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;
    }
};