给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗?
以任意顺序返回这两个数字均可。
示例 1:
输入: [1]
输出: [2,3]
示例 2:
输入: [2,3]
输出: [1,4]
提示:
nums.length <= 30000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/missing-two-lcci
思路:
如果对数组添加从1道N所有的整数,那么这道题就变成了只有两个数出现了一次,其他数出现了两次:260. 只出现一次的数字 III。
复杂度分析:
时间复杂度O(1)
空间复杂度O(1)
var missingTwo = function(nums) {
let ans = 0,n = nums.length;
for(let i = 1;i<=n+2;i++){
ans^=i;
}
for(const num of nums){
ans^=num;
}
let one = 0;
let diff = ans & (-ans);
for(let i = 1;i<=n+2;i++){
if(diff & i) {
one^=i;
}
}
for(const num of nums){
if(diff & num) {
one^=num;
}
}
return [one,one^ans];
};