消失的两个数字
- 难度：Hard
- 题目链接：https://leetcode-cn.com/problems/missing-two-lcci/
题目描述
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
输入: [1]
输出: [2,3]
示例 2:
输入: [2,3]
输出: [1,4]
提示：
nums.length <= 30000
解法：
给原数组中加入数字 1-n，问题就和 数组中数字出现的次数 相同了。
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int len = nums.size();
int x = (len + 1) ^ (len + 2);
for(int i=0;i<len;i++){
x ^= (i+1) ^ nums[i];
}
int mask = x & ~(x-1);
int a = 0, b = 0;
for(int i=0;i<len;i++){
if(nums[i] & mask){
a ^= nums[i];
}else{
b ^= nums[i];
}
}
for(int i=1;i<=len+2;i++){
if(i & mask){
a ^= i;
}else{
b ^= i;
}
}
return {a, b};
}
};