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

• LeetCode：原题
• 难度：中等
• 归类：数组、位运算、数字电路
• 主解法：逐位计数取模

#先给结论

普通异或只能消除出现偶数次的数字，无法消除出现三次的数字，因为：

x ^ x = 0
x ^ x ^ x = x

但二进制的每一位可以独立统计。其他数字都出现三次，所以在任意二进制位上，它们贡献的 1 的数量一定是 3 的倍数。将每一位的计数对 3 取余，剩下的就是只出现一次的数字在该位上的值。

答案的第 bit 位 = 所有数字第 bit 位之和 % 3

这是最容易解释和证明的方案，时间复杂度为 O(32n) = O(n)，额外空间为 O(1)。

#题目描述

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

要求实现线性时间复杂度，并且只使用常量级额外空间。

示例 1：

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

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

#为什么不能直接异或

在“其他数字都出现两次”的版本中，相同数字异或后会变成 0：

x ^ x = 0
0 ^ y = y

但本题的数字出现三次：

x ^ x ^ x
= 0 ^ x
= x

三份 x 并不会被消掉。因此需要记录每一位出现次数对 3 的余数，而不只是奇偶性。

#解法一：逐位计数取模

#核心思路

把所有数字写成 32 位二进制。对第 bit 位进行统计：

• 出现三次的数字，如果该位是 1，会贡献三个 1；
• 出现三次的数字，如果该位是 0，不会贡献 1；
• 因此其他数字在该位贡献的总数一定能被 3 整除；
• 计数对 3 取余后，只可能剩下只出现一次的数字在这一位上的值。

每一位独立恢复后，就得到了完整答案。

#示例：[2, 2, 3, 2]

只需要画出最低两位：

数字      二进制     第 1 位     第 0 位
 2          10          1          0
 2          10          1          0
 3          11          1          1
 2          10          1          0
                       ───        ───
位之和                  4          1
对 3 取余               1          1

将每一位的余数组合起来：

第 1 位 = 1
第 0 位 = 1

答案 = 11₂ = 3

#JavaScript 实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
    let answer = 0;

    // JavaScript 位运算使用 32 位有符号整数，因此检查 0～31 共 32 位
    for (let bit = 0; bit < 32; bit++) {
        let count = 0;

        for (const num of nums) {
            // 无符号右移 bit 位，再取最低位，得到 num 的第 bit 位
            count += (num >>> bit) & 1;
        }

        // 余数为 1，说明只出现一次的数字在这一位上是 1
        if (count % 3 === 1) {
            answer |= 1 << bit;
        }
    }

    return answer;
};

#代码与思路对照

#正确性证明

对于任意二进制位 bit，设只出现一次的数字在该位上的值为 r，其中 r 只能是 0 或 1。

其他数字都出现三次。每个其他数字在该位上要么贡献 0 个 1，要么贡献 3 个 1，所以它们的总贡献可以写成 3k。该位的总计数为：

count = 3k + r

因此：

count % 3 = r

算法对全部 32 位都执行这个过程，所以恢复出的每一位都和只出现一次的数字相同，最终答案正确。

#负数为什么也能处理

JavaScript 的位运算会把 number 转换成 32 位有符号整数，并使用二进制补码表示负数。最高位（第 31 位）是符号位。

算法也统计第 31 位。当答案是负数时：

answer |= 1 << 31;

会设置符号位，JavaScript 会把最终 32 位结果解释成负数。因此在题目给定的 32 位整数范围内，无需单独处理负数。

例如 -3 的 32 位补码为：

11111111 11111111 11111111 11111101

逐位恢复后仍然是这组比特，最终会被解释为 -3。

#解法二：有限状态机

逐位计数需要显式遍历 32 位。还可以用两个整数同时记录所有位的计数模 3，把内层的 32 次循环压缩为位运算。

#每一位需要记录三种状态

对于某个二进制位，我们只关心它出现次数除以 3 的余数：

出现 0 次 → 余数 0
出现 1 次 → 余数 1
出现 2 次 → 余数 2
出现 3 次 → 回到余数 0

三种状态至少需要两个二进制位表示。使用 twos 和 ones：

状态 11 不会使用。

当输入数字的当前位是 1 时，状态循环为：

          再读入一个 1       再读入一个 1       再读入一个 1
   00  ───────────────→  01  ───────────────→  10  ───────────────→  00
余数 0                  余数 1                  余数 2                  余数 0

当输入位是 0 时，状态保持不变。

#状态更新公式

可以用下面两行完成所有 32 位的并行状态转移：

ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;

含义是：

1. ones ^ num：输入位为 1 时，尝试切换“出现一次”的状态；
2. & ~twos：已经进入“出现两次”状态的位不能同时留在 ones；
3. twos ^ num：输入位为 1 时，尝试切换“出现两次”的状态；
4. & ~ones：已经处于“出现一次”状态的位不能同时留在 twos。

注意第二行使用的是更新后的 ones。两行顺序不能随意交换。

#用一位演示三次相同输入

假设某个数字的当前位为 1，连续出现三次：

所以出现三次的数字最终会从状态中消失。全部数字处理完后，其他数字都回到 00，只出现一次的数字停留在 01，因此 ones 就是答案。

#JavaScript 实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
    let ones = 0;
    let twos = 0;

    for (const num of nums) {
        // 更新计数模 3 等于 1 的位，并排除已经处于 twos 的位
        ones = (ones ^ num) & ~twos;
        // 使用更新后的 ones，更新计数模 3 等于 2 的位
        twos = (twos ^ num) & ~ones;
    }

    // 出现三次的位已回到 0，出现一次的数字保留在 ones 中
    return ones;
};

#[2, 2, 3, 2] 的状态变化

为了便于观察，只显示最低两位：

最终 ones = 11₂ = 3。

#两种解法如何选择

面试中建议先讲逐位计数。若面试官继续要求减少常数或推导数字电路，再写状态机，并明确解释 ones、twos 每一位的含义。

#复杂度分析

#逐位计数

• 时间复杂度：O(32n) = O(n)。整数位宽固定为 32。
• 空间复杂度：O(1)。

#有限状态机

• 时间复杂度：O(n)。每个数字只进行常数次位运算。
• 空间复杂度：O(1)。

#边界与陷阱

• 直接异或所有数字：出现三次的数字不会被消除。
• 只统计 31 位：会漏掉符号位，导致负数答案错误；JavaScript 中应统计 32 位。
• 使用算术右移取位：>> 会用符号位补高位；本文使用 >>> 后再 & 1，取位语义更清晰。
• 状态机更新顺序写错：第二行依赖更新后的 ones。
• 把 ones、twos 当成普通计数器：它们的每个二进制位都在独立记录该位出现次数模 3 的状态。
• 忽略语言的位宽规则：JavaScript 位运算只保留 32 位；若题目允许超出 32 位的整数，需要改用 BigInt 或其他方案。
• 使用哈希表计数：虽然正确且为 O(n) 时间，但额外空间为 O(n)，不满足常量空间要求。

#面试官递进追问

#1. 为什么每一位计数后对 3 取余能得到答案？

其他数字在任意位上的贡献都是 3 的倍数。取余后这些贡献全部变成 0，只剩唯一数字在该位上的 0 或 1。

#2. 为什么普通异或在本题失效？

异或只记录每一位出现次数的奇偶性，相当于对 2 取模。本题需要对 3 取模，而 x ^ x ^ x = x，无法消除三个相同数字。

#3. 状态机为什么需要两个变量？

每一位的计数模 3 有 0、1、2 三种状态。一个比特只能表达两种状态，所以至少需要两个比特；两个整数可以并行表示所有 32 位的状态。

#4. 状态 11 为什么不会出现？

更新公式通过 & ~twos 和 & ~ones 保证同一个位置不会同时出现在 ones 和 twos 中，因此 11 是被排除的无效状态。

#5. 如果其他数字出现 k 次怎么办？

逐位计数法可以直接把 % 3 改成 % k。若只出现一次的数字仍然只贡献 0 或 1，每一位取模后仍能恢复答案。状态机则需要设计能够表示模 k 计数的状态和转移公式。

#6. 如果有两个数字只出现一次呢？

本题的取模结果只能得到两个唯一数字在每一位贡献之和的余数，通常无法直接区分它们，需要利用题目的其他条件重新分组；不能原样套用本题方案。

#常见错误回答

• “相同数字异或会消失”：只有出现偶数次时才会消失，出现三次不会。
• 直接背 ones/twos 公式：没有解释每一位对应的模 3 状态，无法证明公式正确。
• 把位计数写成 O(32n) 后认为不是线性时间：位宽 32 是常数，因此渐进复杂度仍为 O(n)。
• 只用十进制次数解释：位运算方案必须说明每个二进制位互相独立。
• 认为负数需要取绝对值：补码的每一位同样满足计数取模性质，无需特殊转换。

#可迁移总结

• 异或本质上是逐位计数对 2 取模；出现 k 次的问题可以尝试逐位计数对 k 取模。
• 位运算可以让一个整数的 32 个二进制位并行维护 32 组状态。
• 难记的位运算公式应先还原成单个二进制位的状态表，再扩展到整个整数。
• 涉及位运算时，要明确语言的整数位宽、符号表示和移位规则。

#刷题后自测

1. 为什么 x ^ x ^ x 不能消除出现三次的 x？
2. 对 [2,2,3,2] 的第 0 位和第 1 位分别计数，取模后得到什么？
3. 状态机中的 00、01、10 分别表示什么？
4. 为什么状态机最后返回 ones，而不是 twos？
5. JavaScript 中为什么需要遍历到第 31 位？