跳到主要内容

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

本节目标

将 32 位整数拆成独立的位计数，按模 3 的余数重建唯一值。

这道题把位运算拓展中的“逐位独立”模型落到具体约束上：其他数都出现三次，只有一个数出现一次，答案的每一位都可以单独恢复。

查看原题

题意与约束​

给定一个非空整数数组 nums，除一个元素只出现一次外，其余元素都恰好出现三次。返回只出现一次的元素。

  • 1 <= nums.length <= 3 * 10^4
  • 每个 nums[i] 都是 32 位有符号整数。
  • 题目保证只有一个元素出现一次。

为什么整体异或不再够用​

上一题中的异或依赖 a ^ a = 0：成对元素会消去。但同一个数出现三次时，a ^ a ^ a = a，它并不会消失，所有三次出现的数都会混在结果里。

这里需要利用新的重复次数规律。对任意一个二进制位，出现三次的数会在该位贡献 0 或 3 个 1，都满足模 3 后为 0；只有答案的该位会留下 1 的余数。

每一位独立统计​

依次处理第 0 到第 31 位。固定某一位后，统计数组中这一位为 1 的次数：

  • 次数除以 3 的余数为 0，答案这一位是 0；
  • 余数不为 0，答案这一位是 1。

每一位的计数不会影响其他位，也没有进位，因此可以把 32 位分别恢复到 answer 中。32 位是固定常数，整体仍只需一次数量级的扫描。

负数与第 31 位​

题目中的整数按 32 位补码表示。第 31 位是符号位；若它为 1，无符号位模式 answer 表示的数应减去 2^32，才能得到对应的有符号答案。

C++ 先把每个 int 转为 uint32_t 再右移，确保读取的是其低 32 位，不依赖负数右移的实现细节。重建时，若第 31 位为 1，先在 int64_t 中计算 answer - 2^32，再转为 int；这个值已在 32 位 int 的范围内，因此不依赖超范围的无符号转有符号转换。

Python 的 int 是无限宽的，负数右移会符号扩展；但对第 0 到第 31 位，(num >> bit) & 1 恰好仍是该数 32 位补码的对应位。循环结束后同样检查第 31 位，并减去 2^32，把无符号重建结果显式还原为负数。

代码实现​

两份源码都进行 32 轮独立计数。C++ 用 uint32_t 保存重建出的位模式；Python 保持普通整数，并在最后显式完成 32 位有符号重建。

C++17
#include <cstdint>
#include <vector>

using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        uint32_t answer = 0;
        for (int bit = 0; bit < 32; bit++) {
            int count = 0;
            for (int num : nums) {
                count += (static_cast<uint32_t>(num) >> bit) & 1U;
            }
            if (count % 3 != 0) {
                answer |= 1U << bit;
            }
        }

        if ((answer & (1U << 31)) != 0) {
            return static_cast<int>(static_cast<int64_t>(answer) - (1LL << 32));
        }
        return static_cast<int>(answer);
    }
};

复杂度分析​

  • 时间复杂度：对 32 个位各扫描一次数组，为 O(32n)，即 O(n)。
  • 额外空间复杂度：只使用计数器、答案和循环变量，为 O(1)。

易错点​

  • 沿用整体异或：三个相同数异或后仍是原数，不能消去。
  • 只统计到最高有效位：负数的符号位也要参与，因此必须固定处理 32 位。
  • C++ 直接右移负数：右移语义不应成为算法前提，应先转为 uint32_t。
  • Python 直接返回位模式：当第 31 位为 1 时会得到非负的大整数，必须减去 2^32。

模式迁移​

当“其余元素都出现相同次数，少数元素留下固定余数”且各位互不影响时，可以尝试逐位计数再取模。重复次数改为 k 时，计数改为模 k；但若出现多个不同的剩余元素，或各位之间存在进位、顺序等关系，就需要重新建模，不能直接套用本题。