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.

Example:

Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]

S: 利用原数组记录数字出现情况 O(n)

要记录每个数字的出现情况要用到extra memory，若要O(1)space只能利用原数组记录。

注意数组的长度一定为n且里面的数字为1-n，每个数字都可以对应到index。遍历数组，对里面的元素i,将第i - 1位置为负数，最后为正数的位的index即为没有出现过的数字

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