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]

 

idea: It's hard to solve without extra space and in O(n) without the condition  1 ≤ a[i] ≤ n. 

Solution 1: for the number a[a[i]-1], if it is positive, assign it to its opposite number, else unchange it. The logic is if i+1 appear in the array, a[i] will be negative, so if a[i] is positive, i+1 doesn't appear in the array.

1 class Solution { 2 public: 3     vector
     
       findDisappearedNumbers(vector
      
       & nums) { 4         vector
       
         res; 5         for (int i=0;i
        
         0)?(-nums[idx]):nums[idx]; 8         } 9         for (int i=0;i
         
          0) res.push_back(i+1);11         }12         return res;13     }14 };
         
        
       
      
     

Solution 2: move nums[i] from positon i to its right position nums[i]-1, swap nums[i] and nums[nums[i]-1]. Finally, if i doesn't equal nums[i]-1, means i+1 doesn't appear in the array. Note the line 6-8

1 class Solution { 2 public: 3     vector
     
       findDisappearedNumbers(vector
      
       & nums) { 4         vector
       
         res; 5         for (int i=0;i
       
      
     

Solution 3: add nums[nums[i]-1] to n, use (nums[i]-1)%n to avoid the overflow of nums[i]-1. Finally, if nums[i]<=n, i+1 is the disappeard number.

1 class Solution { 2 public: 3     vector
     
       findDisappearedNumbers(vector
      
       & nums) { 4         vector
       
         res; 5         int size=nums.size(); 6         for (int i=0;i