448. Find All Numbers Disappeared in an Array&&645. Set Mismatch
题目:
448. Find All Numbers Disappeared in an Array
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
645. Set Mismatch
The set S
originally contains numbers from 1 to n
. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.
Given an array nums
representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.
思路:
448和645具有相似的思路。两道题的共同点在于:元素的大小均为 [1,n]。448要求找出未出现的数字,645要求找出出现了两次的数字和未出现的数字。
由于元素的下标为[0,n-1],则元素的大小减去1得到的即为某个元素的下标,因此可以利用元素大小与下标之间的关系寻找特殊的数字。
对于448,遍历整个数组,通过元素的大小减去1得到下标。若该下标对应的元素为正,则将其乘以-1,变为负数;若该下标对应的元素为负,证明该下标之前已经出现过了一次,不作处理。通过这一次的遍历,仍然为正的元素所对应的下标再加1即为未出现过的元素。
对于645,遍历整个数组,通过元素的大小减去1得到下标。若该下标对应的元素为正,则将其乘以-1,变为负数;若该下标对应的元素为负,证明该下标之前已经出现过了一次,将该下标+1加入result中。通过这一次的遍历,仍然为正的元素所对应的下标再加1即为未出现过的元素。
代码:
448.
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> ans;
for (int i = ; i < (signed) nums.size(); i++) {
int index = abs(nums[i]) - ;
if (nums[index] > )
nums[index] *= -;
else
continue;
}
for (int i = ; i < (signed) nums.size(); i++)
if (nums[i] > )
ans.push_back(i + );
return ans;
}
};
645.
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> ans;
for (int i = ; i < (signed) nums.size(); i++) {
int index = abs(nums[i]) - ;
if (nums[index] > ) {
nums[index] *= -;
} else {
ans.push_back(index + );
}
}
for (int i = ; i < (signed) nums.size(); i++) {
if (nums[i] > )
ans.push_back(i + );
}
return ans;
}
};
最新文章
- tomcat乱码原因--基本的编码问题
- Windows Phone 二十一、联系人存储
- vertical-align 垂直居中
- StgCreateDocfileOnILockBytes复合文档
- Magento文件系统目录结构
- linux dmesg命令参数及用法详解(linux显示开机信息命令)
- CODESOFT中线条形状该如何绘制
- Android IOS WebRTC 音视频开发总结(三九)-- win10升级为何要p2p
- Linux下Redis的安装、配置操作说明
- 用js实现两个select下拉框之间的元素互相移动
- Openstack_O版(otaka)部署_准备环境和依赖软件
- Redis之Hash
- Interface Development
- C#现代代码风格指南
- 开发 chrome 扩展 GitHub-Remarks 的一些想法以及遗憾
- Condition条件变量
- 2017.2.6Redis连接问题排查
- 处理ajax数据;数据渲染
- idea for mac 最全快捷键整理
- 百度echart初用总结