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]

掃過第一遍把出現過的數標記起來。標記的方法就是把對應到的index的數變成負值。第二次掃描就可以找到只要數值為正的index對應到的數字就是沒出現過的數字。

// Two Pass Method
vector<int> findDisappearedNumbers(vector<int>& nums) { // time: O(n); space: O(1)
    vector<int> res;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        int idx = abs(nums[i]) - 1;
        nums[idx] = nums[idx] > 0 ? -nums[idx] : nums[idx];
    }
    for (int i = 0; i < n; ++i) {
        if (nums[i] > 0) {
            res.push_back(i + 1);
        }
    }
    return res;
}