算法实战：位运算求解两数之和、唯一数字及缺失数字

36. 只出现一次的数字 II

137. 只出现一次的数字 II - 力扣（力扣）

题目描述

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

题目示例

解法思路

统计每一位上 1 出现的总次数：

• 数组中其他数字都出现三次，因此某一位上的 1 的总数必然是 3 的倍数。
• 若某一位总和模 3 余 1，说明目标数字在该位为 1；否则为 0。
• 遍历 32 个比特位即可还原目标数字。

C++ 代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int x : nums) {
                sum += ((x >> i) & 1);
            }
            ret |= ((sum % 3) << i);
        }
        return ret;
    }
};

流程解析

这种方法虽然时间复杂度是 O(32N)，但空间复杂度仅为 O(1)，且不需要额外哈希表，非常适合对空间敏感的场景。

37. 消失的两个数字

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

题目描述

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

题目示例

解法思路

结合异或性质分组解决：

1. 将数组内所有数与 [1, n+2] 区间所有数全部异或，得到两个消失数字的异或值 ret。
2. 找到 ret 中最右侧为 1 的位，该位表明两个消失数字在此位不同。
3. 根据该位将数字分为两组分别异或，每组抵消后剩下的即为一个消失的数字。

C++ 代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        for (int x : nums) ret ^= x;
        for (int i = 1; i <= nums.size() + 2; i++) ret ^= i;

        // 找到最右侧为 1 的位
        int bit = 0;
        while (!((ret >> bit) & 1)) bit++;

        int a = 0, b = 0;
        for (int x : nums) {
            if ((x >> bit) & 1) b ^= x;
            else a ^= x;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if ((i >> bit) & 1) b ^= i;
            else a ^= i;
        }
        return {a, b};
    }
};

流程解析

通过提取差异位进行分组，巧妙地将'找两个数'的问题转化为两次'找单个数'的问题，避免了排序带来的额外开销。