class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
}
};
面试题 17.19. 消失的两个数字
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
输入: [1]
输出: [2,3]
示例 2:
输入: [2,3]
输出: [1,4]
提示：
nums.length <= 30000原站题解
python3 解法, 执行用时: 76 ms, 内存消耗: 18.1 MB, 提交时间: 2022-08-26 14:45:45
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
'''
由于从 1 到 n 的整数中有两个整数消失，其余每个整数都在数组中出现一次，因此数组的长度是 n − 2。
在数组中的 n - 2 个数后面添加从 1 到 n 的每个整数各一次，则得到 2n − 2 个数字，
其中两个在数组中消失的数字各出现一次，其余每个数字各出现两次。
'''
xorsum = 0
n = len(nums) + 2
for num in nums:
xorsum ^= num
for i in range(1, n + 1):
xorsum ^= i
lsb = xorsum & (-xorsum)
type1 = type2 = 0
for num in nums:
if num & lsb:
type1 ^= num
else:
type2 ^= num
for i in range(1, n + 1):
if i & lsb:
type1 ^= i
else:
type2 ^= i
return [type1, type2]