面试题 17.19 消失的两个数字：位运算实战解析

面试题 17.19 消失的两个数字

题目链接：

面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

题目描述：

题目示例：

解题思路

这道题本质上是 268. 丢失的数字 和 260. 只出现一次的数字 III 的结合体。

核心在于利用异或运算的性质：

1. 相同的数异或为 0。
2. 任何数与 0 异或为其本身。

我们将数组中的元素与区间 [1, n+2] 的所有整数一起异或。由于除了两个缺失的数字外，其他数字都出现了两次（一次在数组，一次在区间），它们会相互抵消。最终剩下的结果就是那两个缺失数字的异或值（记为 a ^ b）。

既然 a != b，那么 a ^ b 的结果中至少有一位是 1。我们可以根据这一位将所有的数字分为两组，每组包含一个缺失数字。再分别对两组进行异或，即可还原出 a 和 b。

C++ 实现方案

这里提供两种常见的位运算实现方式。

方法一：提取最低有效位

直接利用 x & (-x) 快速提取二进制中最右侧的 1。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int temp = 0;
        // 数组元素异或
        for (auto& x : nums) temp ^= x;
        // 区间 [1, n+2] 异或
        for (int i = 1; i <= nums.size() + 2; i++) temp ^= i;
        
        // temp 现在是 a ^ b，提取最右边的 1
        int ls = temp & (-temp);
        
        int a = 0, b = 0;
        // 分组异或
        for (auto& x : nums) {
            if (x & ls) a ^= x;
            else b ^= x;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if (i & ls) a ^= i;
            else b ^= i;
        }
        return {a, b};
    }
};

方法二：循环查找差异位

如果不熟悉位运算技巧，也可以循环移位找到第一个不同的比特位。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int tmp = 0;
        for (auto x : nums) tmp ^= x;
        for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
        
        // 找出 a, b 中比特位不同的那一位
        int diff = 0;
        while (true) {
            if (((tmp >> diff) & 1) == 1) break;
            else diff++;
        }
        
        int a = 0, b = 0;
        for (int x : nums)
            if (((x >> diff) & 1) == 1) b ^= x;
            else a ^= x;
        
        for (int i = 1; i <= nums.size() + 2; i++)
            if (((i >> diff) & 1) == 1) b ^= i;
            else a ^= i;
            
        return {a, b};
    }
};

算法总结

---

这种位运算解法避免了额外的哈希表开销，空间复杂度仅为 O(1)，非常适合面试场景下的性能要求。理解异或消去律和分组思想，能解决很多看似复杂的计数问题。