LeetCode 面试题 17.19. 消失的两个数字
题目描述
题意分析
原本包含从 $1$ 到 $N$ 的每个整数各一次，现在恰好缺少两个数，剩余元素以无序数组给出。数组长度是 $N-2$，所以可以先用
nums.length + 2得到完整值域的上界。要在 $O(N)$ 时间、$O(1)$ 额外空间内找出两个缺失值。比较排序需要 $O(N\log N)$ 时间，保存全部元素的集合需要 $O(N)$ 空间；这里利用异或在常数空间内抵消已有数字。题目允许按任意顺序返回答案。
解法：按位异或拆分
核心思路
[!blue]
异或满足
v ^ v = 0、v ^ 0 = v，并且交换顺序不影响结果。设两个缺失数为a、b，将完整值域[1, N]和实际数组的所有元素一起异或：已经出现的数各有两份，会全部抵消，最后只剩xor = a ^ b。只知道
a ^ b还不能直接读出两个数，需要再把它们分开。由于a、b不同，xor一定非零；它的任意一个为 $1$ 的二进制位，都表示a与b在该位不同。用
lowbit = xor & -xor取最低的那个 $1$。在补码表示中，取负会把比最低 $1$ 更高的位取反，而这个最低 $1$ 及其后面的 $0$ 保持不变；与原值相与后就只留下这一位。这里只把它当作分组标记，不需要知道它是第几位。再次遍历完整值域和实际数组，把
(value & lowbit) == 0的数放入一组，其余放入另一组，各自异或。两个缺失数在标记位不同，所以一定进入不同组；其他数的两份值完全相同，一定进入同一组并互相抵消。因此两组分别只剩一个缺失数。分组必须同时处理完整值域和实际数组，且两边使用同一个
lowbit。代码最后仅通过一次交换将答案按升序放置，不影响题目允许的任意返回顺序；数组为空时，完整值域为[1, 2]，上述过程也自然成立。
解题步骤
- 令
n = nums.length + 2，将[1, n]与nums全部异或，得到两个缺失数的异或值。- 计算
lowbit = xor & -xor，初始化两组累计值a = 0、b = 0。- 分别遍历
[1, n]和nums，按标记位是否为零分组异或。- 两组累计值就是答案，整理返回顺序后返回。
代码实现
// 取 xor 的最低位 1，把所有数按该位分成两组，分别异或即可得到 a 和 b。
class Solution {
public int[] missingTwo(int[] nums) {
// 当前数组少了两个数，由长度恢复完整值域上界。
int n = nums.length + 2;
int xor = 0;
for (int i = 1; i <= n; i++) {
xor ^= i;
}
for (int num : nums) {
xor ^= num;
}
// 两个缺失数在这一位不同，可分别进入两组抵消。
int lowbit = xor & -xor;
int a = 0;
int b = 0;
for (int i = 1; i <= n; i++) {
if ((i & lowbit) == 0) {
a ^= i;
} else {
b ^= i;
}
}
for (int num : nums) {
if ((num & lowbit) == 0) {
a ^= num;
} else {
b ^= num;
}
}
if (a > b) {
int swapValue = a;
a = b;
b = swapValue;
}
return new int[] {
a,
b
};
}
}
// 取 xor 的最低位 1，把所有数按该位分成两组，分别异或即可得到 a 和 b。
func missingTwo(nums []int) []int {
// 当前数组少了两个数，由长度恢复完整值域上界。
n := len(nums) + 2
xor := 0
for i := 1; i <= n; i++ {
xor ^= i
}
for _, num := range nums {
xor ^= num
}
// 两个缺失数在这一位不同，可分别进入两组抵消。
lowbit := xor & -xor
a, b := 0, 0
for i := 1; i <= n; i++ {
if i&lowbit == 0 {
a ^= i
} else {
b ^= i
}
}
for _, num := range nums {
if num&lowbit == 0 {
a ^= num
} else {
b ^= num
}
}
if a > b {
a, b = b, a
}
return []int{
a,
b,
}
}
复杂度分析
- 时间复杂度：$O(N)$，完整值域和输入数组分别扫描两遍，扫描次数固定。
- 空间复杂度：$O(1)$，只使用异或值、标记位和两个分组累计值。
关键点总结
[!green]
- 理论值域和实际数组都要参与两轮操作。
- 两轮分组必须采用完全相同的标记位。
易错点总结
[!yellow]
- 忘记数组长度加二，会构造错误的完整值域。
- 分组时漏掉实际数组，已有元素无法抵消。
- 按标记位结果等于一判断，会在标记位不是最低位时失败。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 268. 丢失的数字 | 简单 | 原题只缺一个数，本题缺两个，合并全集与数组的异或结果只得到两缺失值的异或。 |
| 260. 只出现一次的数字 III | 中等 | 利用两缺失值异或中的一位把它们分组，再各组抵消，复用寻找两个单次值的方法。 |