算法实战：位运算解决两数之和、唯一数字及消失数字问题

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

题目示例

输入：nums = [2,2,3,2] 输出：3

解题思路

如果允许使用哈希表，空间复杂度会是 O(N)。但题目通常隐含要求线性时间且常数空间。这里利用比特位计数是个很巧妙的技巧：

假设我们要找的数是 ret。数组中其他数都出现了三次，意味着它们在每一个比特位上的 1 的总数一定是 3 的倍数。唯独那个只出现一次的数，会在某些位上贡献额外的 1。

因此，我们可以遍历整数的 32 个比特位，统计所有数字在该位上 1 出现的总次数。如果 sum % 3 != 0，说明目标数字在这一位上是 1，否则是 0。通过这种方式逐位还原出目标数字。

代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0; // 用于存储结果
        for (int i = 0; i < 32; i++) { // 遍历 32 个比特位
            int sum = 0;
            for (int x : nums) {
                sum += ((x >> i) & 1); // 累加第 i 位的值
            }
            // 如果某一位的 1 的个数不是 3 的倍数，则目标数字该位为 1
            ret |= ((sum % 3) << i);
        }
        return ret;
    }
};

流程解析

38. 消失的两个数字

题目链接

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

题目描述

给定一个包含从 0 到 n 的所有整数的数组，其中有两个数字缺失。找出这两个缺失的数字。

题目示例

输入：nums = [1, 0] 输出：[2, 3] (顺序不限)

解题思路

这道题其实是'丢失的数字'和'只出现一次的数字 III'的组合变体。核心思路依然是异或消除重复项：

1. 整体异或：将数组中的所有数，以及区间 [1, n+2] 内的所有数全部异或一遍。由于成对出现的数会抵消，最终结果 ret 等于那两个消失数字的异或值（a ^ b）。
2. 分组依据：因为 a 和 b 不同，它们的异或结果 ret 中至少有一位是 1。找到这个最右侧的 1 所在的位（记为 x），这意味着 a 和 b 在这一位上一个为 0，一个为 1。
3. 分组异或：根据这一位是 0 还是 1，将所有数字分成两组分别异或。这样就能把 a 和 b 分离开，各自组内其他成对的数都会抵消，剩下的就是我们要找的两个数。

代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        int a = 0;
        int b = 0;
        
        // 第一步：计算所有数与完整区间的异或和
        for (int num : nums) ret ^= num;
        for (int i = 1; i <= nums.size() + 2; i++) ret ^= i;
        
        // 第二步：找到 ret 中最右侧为 1 的位
        int x = 0;
        while (!((ret >> x) & 1)) x++;
        
        // 第三步：根据该位分组异或
        for (int num : nums) {
            if (((num >> x) & 1) == 0) a ^= num;
            else b ^= num;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if (((i >> x) & 1) == 0) a ^= i;
            else b ^= i;
        }
        
        return {a, b};
    }
};

流程解析