LeetCode-Array-448. Find All Numbers Disappeared in an Array

問題：Givenan array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appearonce.Find all the elements of [1, n] inclusive that do not appear in thisarray.Could you do it without extra space and in O(n) runtime? You may assumethe returned list does not count as extra space.

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

思考：現将數組按元素值，從小到大排序，并建立一個vectorresult儲存最後的輸出。如果第一個元素非1，則将從1到nums[0]-1的值都存在result數組裡面。接着看中間的元素，如果某一個值與前一個值相等，或者等于前一個值加1，則可繼續。若大于，則将這其中少的幾個值存在result數組中。再看最後一個值nums[n-1]，将nums[n-1]和n之間值存在result中。

代碼：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
      sort(nums.begin(),nums.end());  
       int n=nums.size();  
       vector<int> result;  
       if(!n)  return result;  
           

int idx=1;  
       //1和nums[0]之間的  
       while(nums[0]>idx)  
           result.push_back(idx++);  
           //中間部分  
       for(int i=1;i<n;i++)  
       {  
           if(nums[i]==nums[i-1]||nums[i]==nums[i-1]+1)  
           continue;  
           if(nums[i]>nums[i-1]+1)  
           {  
               for(int j=nums[i-1]+1;j<nums[i];j++)  
               result.push_back(j);  
           }  
       }  
       idx=nums[n-1];  
       //nums[n-1]和n之間  
       while(idx!=n)  
       {  
           result.push_back(++idx);  
       }  
       return result;
    }
};