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]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一个萝卜一个坑，不对付就换到自己的位置就行了。

要用while没换到底就一直换。

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

第一的代码 ，人家这个在我的个人理解看来很巧妙

这个位置应该有个数他没有换过去，而是置换成负数，这样表示这里应该有个数。时间复杂度就是1.空间复杂度也是1.满足题目要求没有任何多余的空间。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> result;
        if(nums.empty())
            return result;
        for(int i = 0; i < nums.size(); i++){
            nums[abs(nums[i]) - 1] = 0-abs(nums[abs(nums[i]) - 1]);
        }
        for(int i =0; i < nums.size(); i++){
            if(nums[i] > 0)
                result.push_back(i + 1);
        }
        return result;
    }
};