Find All Numbers Disappeared in an Array

Description

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]

Solutions

My solution

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        while(i < n){
            if(nums[i] == i + 1 || nums[nums[i] - 1] == nums[i]){
                ++i;
            }else{
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        vector<int> ans;
        for(int j = 0; j < n; ++j){
            if(nums[j] != j + 1)
                ans.push_back(j + 1);
        }
        return ans;
    }
};

The running time is O(n). Proof:

We say that a number nums[i] is at its correct position if nums[i] == i + 1. After each swap statement, at least one number, i.e., nums[i], is put to its correct position. Since we can put at most n numbers to their correct positions and once a number is put to its correct position, it no longer moves. Thus, the swap statement is executed at most n times. And the ++i statement is also executed at most n times. So the running time of the while loop is O(n). The remaining is trivial.

A better solution

This solution is more efficient, though the time complexity is the same. It also modifies the input array, but the modification can be revert.

The idea to mark the numbers that appears in the array with negative values. Another similar idea is to mark these numbers by adding n(but overflow may occur).

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        // nums[i] < 0 <=> i+1 is in the array
        for(int i = 0; i < n; ++i){
            int idx = abs(nums[i]) - 1;
            if(nums[idx] > 0)
                nums[idx] = -nums[idx];
        }
        vector<int> ans;
        for(int i = 0; i < n; ++i){
            if(nums[i] > 0)
                ans.push_back(i + 1);
        }
        return ans;
    }
};