给定一个数组,包含从 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];};
