题目
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
输入: [1] 输出: [2,3]
示例 2:
输入: [2,3] 输出: [1,4]
解题
方法一：位运算
此题是 只出现过一次的两个数 的改版。
由于nums是1~N的，并且少了两个数，总数为N-2
那么再补上1~N的数，总数为2N-2
对于重复的数，位运算可以消掉，后续就和只出现过一次的两个数一样，来求得两个数
class Solution { public: vector<int> missingTwo(vector<int>& nums) { int n=nums.size(); int m=0; for(int num:nums){ m^=num; } for(int i=1;i<=n+2;i++){ m^=i; } int mask=m&(-m); vector<int> res(2); for(int num:nums){ if(num&mask){ res[0]^=num; }else{ res[1]^=num; } } for(int i=1;i<=n+2;i++){ if(i&mask){ res[0]^=i; }else{ res[1]^=i; } } return res; } };
方法二：抽屉原理
数组后补两个-1，使用抽屉原理对数组进行排序，O(n)的时间复杂度，再遍历一遍数组找到两个-1的位置就是答案
class Solution { public: vector<int> missingTwo(vector<int>& nums) { vector<int> ans; nums.push_back(-1); nums.push_back(-1); for(int i=0;i<nums.size();i++){ while(nums[i]!=-1&&nums[i]!=i+1){ swap(nums[i],nums[nums[i]-1]); } } for(int i=0;i<nums.size();i++) if(nums[i]==-1) ans.push_back(i+1); return ans; } };
