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]

并要求空间复杂度为常数，时间复杂度O(n)

Solution

题设给定了两个条件：

1.数组中的数的范围是[1,n]，其中n是数组长度

2.有的数出现了两次，有的数出现了一次

也即，出现了两次的数的个数等于没出现的数的个数。

可以根据这两个条件得到：出现了两次的数覆盖了其它的数导致有的数没有出现，而只出现了一次的数既没有被覆盖，也没有覆盖其它的数。

因此，可以遍历检查，并试图将所有的数移动到指定的位置，比如将数4放到数组角标为3的位置，数1放到数组角标为0的位置，数n放到数组角标为n-1的位置。移动时先将原来的位置的值记为-1，代表空缺。再保存目标位置的数（以防覆盖），以便做下一次移动操作，直到目标位置的数是-1（即空缺，不会有数被覆盖）或者目标位置的数就是被移动的数（这个数出现了两次）为止。

这样就相当于完成了某种交换，去除了出现两次的数，而数组职为-1的位置所代表的数就是本来没有出现的数。

 

例子：[ 4, 3, 2, 7, 8, 2, 3, 1]

检测到4没有在指定位置：

[-1, 3, 2, 4, 8, 2, 3, 1] 取4移至nums[3]处，并使下一次试图存放7

[-1, 3, 2, 4, 8, 2, 7, 1] 7放在nums[6]处，并使下一次试图存放3

[-1, 3, 3, 4, 8, 2, 7, 1] 3放在nums[2]处，并使下一次试图存放2

[-1, 2, 3, 4, 8, 2, 7, 1] 2放在nums[1]处，并使下一次试图存放3

3已放在nums[2]处，不操作

 

检测到8没有在指定位置：

[-1, 2, 3, 4,-1, 2, 7, 8] 取8移至nums[7]处，并使下一次试图存放1

[ 1, 2, 3, 4,-1, 2, 7, 8] 1放在nums[0]处，由于nums[0]空缺，直接放入即可

 

检测到2没有在指定位置

[ 1, 2, 3, 4,-1,-1, 7, 8] 2已放在nums[1]处，不操作

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums)
    {
        for(int i = 0; i < (int) nums.size(); i++)
        {
            int p, q;
            if(nums[i] != i + 1 && nums[i] != -1)
            {
                p = nums[i];
                nums[i] = -1;
                while(true)
                {
                    q = nums[p - 1];
                    nums[p - 1] = p;
                    if(p == q || q == -1) break;
                    p = q;
                }
            }
        }
        int cnt = 0;
        for(int i = 0; i < (int) nums.size(); i++)
        {
            if(nums[i] == -1) nums[cnt++] = i + 1;
        }
        nums.resize(cnt);
        return nums;
    }
};