5.4 位运算专题：LeetCode 137. 只出现一次的数字 II

1. 题目链接

LeetCode 137. 只出现一次的数字 II

2. 题目描述

给定一个整数数组 nums，其中每个元素均出现 三次，除了一个元素只出现 一次。请找出这个只出现一次的元素。
要求：

• 时间复杂度为 O(n)，空间复杂度为 O(1)。

示例：

• 输入：nums = [2,2,3,2] → 输出：3
• 输入：nums = [0,1,0,1,0,1,99] → 输出：99

3. 示例分析

1. 常规测试：
   • nums = [3,3,3,5] → 输出 5。
2. 负数测试：
   • nums = [-1,-1,-1,-2] → 输出 -2。
3. 大数测试：
   • nums = [10000,10000,10000,1] → 输出 1。

4. 算法思路

核心思想：逐位统计 + 模 3 运算

1. 逐位统计：
   • 整数为 32 位，对每一位 i（0 ≤ i < 32），统计所有数字在该位上为 1 的总次数。
2. 模 3 运算：
   • 若某一位的总次数 sum % 3 == 1，说明只出现一次的数在该位上为 1，否则为 0。
3. 构造结果：
   • 将所有满足 sum % 3 == 1 的位设置为 1，得到最终结果。

数学原理：

• 出现三次的数的每个二进制位之和必为 3 的倍数，模 3 后为 0。
• 只出现一次的数在每个二进制位上的值决定了该位模 3 的结果。

5. 边界条件与注意事项

1. 负数处理：
   • 使用算术右移（保留符号位），确保负数二进制位的正确统计。
2. 整数溢出：
   • 输入数组中的数可能在 INT_MIN 到 INT_MAX 之间，但算法本身不涉及运算溢出。
3. 全零情况：
   • 若所有位统计均为 0，结果为 0（题目保证存在唯一解，无需额外处理）。

6. 代码实现

class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret = 0;
        // // 逐个处理 ret 的每一个比特位（共32位）
        for (int i = 0; i < 32; i++) 
        {
            int sum = 0;
            // 统计第i位为1的总次数
            for (int x : nums) 
				if (((x >> i) & 1) == 1) sum++;
            sum %= 3;
            // 若模3余1，设置该位为1
            if (sum == 1) ret |= (1 << i);

        }
        return ret;
    }
};

与其他方法的对比

位运算法的优势

1. 无额外空间：仅需常数空间，适合内存敏感场景。
2. 兼容性：正确处理负数和大数，无需类型转换。
3. 确定性：严格线性时间复杂度，不受数据分布影响。

分步解析

1. 初始化结果变量：

   int ret = 0;
   

   • ret 初始为 0，所有二进制位均为 0。

2. 逐位统计与构造结果：

   • 外层循环：遍历 32 位中的每一位。

     for (int i = 0; i < 32; i++)
     

   • 内层循环：统计当前位 i 的总出现次数。

     for (int x : nums) {
         if (((x >> i) & 1) == 1) sum++;
     }
     

   • 模 3 运算：

     sum %= 3;
     

   • 设置结果位：

     if (sum == 1) ret |= (1 << i);
     

总结

位运算法通过逐位统计和模 3 运算，以 O(n) 时间复杂度和 O(1) 空间复杂度高效解决了“只出现一次的数字 II”问题。其核心思想是将问题分解到每个二进制位上，利用数学性质过滤重复元素。相较于哈希表法和排序法，位运算法在空间和效率上表现更优，尤其适合处理大规模数据或内存受限的场景。

扩展思考：

• 通用性：若问题改为“其他元素出现 k 次”，可将模 3 改为模 k。
• 有限状态机：通过位运算模拟三进制状态转移，可进一步优化常数时间。

关键点：

• 理解二进制位的独立性及模运算的过滤作用。
• 处理负数时算术右移的特性。