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]

题目分析

第一次做的时候就是普通想法，先将vector排序，然后遍历数组，将未出现的数字存到结果中去。第二种方法是遍历数组，将元素作为下标对应的元素取负，最后遍历数组，不是负数的位置就是没出现的元素。

代码

排序

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        vector<int> result;
        int flag = 1;
        int j = 0;
        for (int i = 1;i < len+1;i++) {
            while(nums[j] <= i && j != len){
                j++;
            }
            j--;
            if (nums[j] != i) {
                result.push_back(i);
            }
        }
        return result;
    }
};

取负数

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++){
            nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1]);
        }
        vector<int> result;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] > 0){
                result.push_back(i+1);
            }
        }
        return result;
    }
};