面试题 17.19. 消失的两个数字

Difficulty: 困难

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1:

1
2

输入: [1]
输出: [2,3]

示例 2:

1
2

输入: [2,3]
输出: [1,4]

提示：

  • nums.length <= 30000

Solution

Language: ****

 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
30
31
32

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        nums.push_back(-1);
        nums.push_back(-1);
        int n = nums.size();
        
        
        for(int i=0;i<n;++i) {
            //[2,3,-1,-1]
            //[-1,2,3,-1]
            while(1) {
               // break;
                if(nums[i] == -1) break;
                if(nums[i] == 1 + i ) break;
                // 交换到对应的位置
                swap(nums[i], nums[nums[i] - 1]);
                 
            }
            
        }
        vector<int> res;
        int cnt = 2;
        for(int i=0;cnt && i<n;++i)
            if(nums[i] == -1) res.push_back(1+i),--cnt;
        //for(int u: nums) printf("%d ",nums[u]);


        return  res;

    }
};