分析
只需要O(n)遍历的关键在于要用负号识别当前数是否用过
- 遍历每个元素,对索引进行标记,将对应索引位置的值变为负数
- 遍历下索引,看看哪些索引位置上的数不是负数的,位置上不是负数的索引,对应的元素就是不存在的
C++ 代码
class Solution {
public:
vector<int> ans;
vector<int> findDisappearedNumbers(vector<int>& nums) {
for(int i=0;i<nums.size();i++)
{
int idx=abs(nums[i])-1;
if(nums[idx]>0) nums[idx]*=-1; //只有当前索引对应的数是整数,说明这个数此前还没有用过,*-1表示用过
}
for(int i=0;i<nums.size();i++)
if(nums[i]>0) //如果当前i对应的数大于零,说明i+1没有用过,加入到答案数组
ans.push_back(i+1);
return ans;
}
};