448. Find All Numbers Disappeare

描述

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.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

思路

我们把数组[4,3,2,7,8,3,1]里边的元素看作是index，每当出现这个索引，我们把索引位置上的元素变成负数，这样，哪个位置上的数是正数，说明索引没有出现过，即，说明数组里边的元素没有出现过

代码

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        
        int n =nums.size();
        vector<int> res;
        
        for(int i = 0;i<n;i++)
        {
            int index = abs(nums[i]) - 1;
            if(nums[index] > 0)//如果num[index]<0,说明我们标记过了
                nums[index] = -nums[index];
        }
        
        for(int i = 0;i<n;i++)
        {
            if(nums[i]>0)
                res.push_back(i+1);
        }
        
        return res;
        
    }
};