LeetCode LCR 004. 只出现一次的数字 II

约 8 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 LCR 位运算
目录

题目描述

✅ LCR 004. 只出现一次的数字 II

题意分析

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

题目附带的进阶要求是线性时间复杂度、常数额外空间。这两条一起把哈希表计数、排序后扫描全部排除了：前者是 $O(n)$ 空间，后者是 $O(n \log n)$ 时间。只剩下「一边扫一边把信息压进常数个变量里」这一条路。

「出现三次」是全部结构信息的来源。它意味着如果把所有数按二进制的某一位分开统计，那一位上 $1$ 的总个数一定是「三倍的某个数」再加上「答案在这一位上是不是 $1$」。换句话说，对 $3$ 取余会把所有重复元素的贡献整体抹平，只留下答案。这个观察对每一位独立成立，位与位之间互不干扰。

需要额外留意的约束是元素可以是负数，取值覆盖完整的 32 位有符号范围。这意味着第 $31$ 位（符号位）也必须参与统计和还原，不能只处理低 31 位，否则负数答案会被还原成一个巨大的正数。

边界方面：数组长度至少为 $1$（只有答案本身时直接返回它，逻辑天然覆盖）；答案可能是 $0$，此时所有位的余数都是 $0$，返回值自然为 $0$，不需要特判。

解法：位运算压缩状态

核心思路

先看经典的「出现两次」版本（136 题）：整体异或即可，因为异或满足 $x \oplus x = 0$，成对的数自动消掉。但异或的自消周期是 $2$，而这里重复次数是 $3$，异或完全不起作用——2 ^ 2 ^ 2 = 2，重复元素消不掉。这就是暴力思路的瓶颈：需要一个「模 $3$ 归零」的运算，而按位异或只提供「模 $2$ 归零」。

关键观察是把整数拆成独立的 32 个二进制位。对固定的第 $i$ 位，所有出现三次的元素在这一位上要么各贡献 $3$ 个 $1$、要么各贡献 $0$ 个 $1$，无论哪种，它们的总贡献都是 $3$ 的倍数。因此：

\[\Big(\sum_{x \in nums} (x \gg i) \operatorname{\&} 1\Big) \bmod 3 = \text{答案的第 } i \text{ 位}\]

于是要维护的状态非常直白：对每一位 $i$，用 cnt 记录数组中所有元素在第 $i$ 位上为 $1$ 的个数；cnt % 3 就是答案在第 $i$ 位上的取值。逐位算完再用 answer |= bit << i 把 32 位拼回一个整数。整个过程只用了 answer、cnt、i 三个标量，满足常数空间；外层固定 $32$ 轮、内层扫一遍数组，是 $O(32n) = O(n)$。

负数的处理是免费的：在补码表示下，第 $31$ 位就是符号位，按同样规则统计和写回，拼出来的 32 位模式就是正确的补码。Java 里 answer 本身就是 32 位 int，cnt << 31 自然落到符号位；Go 的 int 是 64 位，所以用 int32 累加、最后转回 int，避免符号位被当成普通位而丢掉负号。

解题步骤

  • 外层固定遍历 $32$ 位，i 从 $0$ 到 $31$。必须跑满 $32$ 位而不是「到最大值的位数为止」，因为负数在补码下高位全是 $1$，截断会丢掉符号信息。
  • 内层扫一遍数组，累加 x >> i & 1。右移再与 $1$ 是取第 $i$ 位的标准写法；这里的移位对负数用算术右移也没问题，因为只取最低那一位。
  • cnt %= 3。这一步是整道题的核心：所有出现三次的元素在这一位上的贡献之和必然是 $3$ 的倍数，取余后被整体抹掉，剩下的 $0$ 或 $1$ 就是答案在这一位上的值。
  • answer |= cnt << i 把这一位写回答案。用「或」而不是「加」在这里等价（每位只写一次），但「或」更能表达「组装位模式」的语义。
  • Go 侧用 int32 累积再转 int。因为 Go 的 int 是 64 位，若直接用 int 累积，1 << 31 会得到 $2147483648$ 这个正数，而不是期望的 $-2147483648$；换成 int32 后符号位被正确解释，转回 int 时会做符号扩展。
  • 循环结束直接返回 answer，不需要任何后处理。

以 nums = [2, 2, 3, 2] 走一遍，二进制分别是 10、10、11、10，期望答案 3。i = 0：四个数的第 $0$ 位依次是 $0, 0, 1, 0$，cnt = 1，1 % 3 = 1，answer |= 1 << 0，此时 answer = 1。i = 1：第 $1$ 位依次是 $1, 1, 1, 1$，cnt = 4，4 % 3 = 1，answer |= 1 << 1，此时 answer = 3——注意三个 2 贡献的那 $3$ 个 $1$ 被取余整体消掉了，只剩 3 自己的那一个。i = 2 到 i = 31：所有数的这些位都是 $0$，cnt = 0，余数为 $0$，answer 不变。最终返回 3。如果把 [2, 2, 3, 2] 换成 [-2, -2, -2, 3]，同样的流程会在 i = 31 处得到 cnt = 3、余数 $0$，从而正确地保持答案为正。

代码实现

class Solution {
    public int singleNumber(int[] nums) {
        int answer = 0;
        // 32 位必须跑满，第 31 位是符号位，截断会算错负数答案。
        for (int i = 0; i < 32; ++i) {
            int cnt = 0;
            for (int x : nums) {
                cnt += x >> i & 1;
            }
            // 出现三次的元素在这一位上的贡献是 3 的倍数，取余后被整体抹掉。
            cnt %= 3;
            answer |= cnt << i;
        }
        return answer;
    }
}

func singleNumber(nums []int) int {
    // Go 的 int 是 64 位，用 int32 累积才能让第 31 位正确表示符号。
    var answer int32
    for i := 0; i < 32; i++ {
        cnt := 0
        for _, x := range nums {
            cnt += x >> i & 1
        }
        cnt %= 3
        answer |= int32(cnt) << i
    }
    return int(answer)
}

复杂度分析

  • 时间复杂度：$O(n)$。外层是固定的 $32$ 轮，与输入规模无关；内层扫一遍数组做常数操作，总共 $32n$ 次基本运算，常数因子被视为定值。
  • 空间复杂度：$O(1)$。只用了 answer、cnt、i 三个标量，没有哈希表、没有排序、没有任何随 $n$ 增长的结构，正好满足题目的进阶要求。

关键点总结

  • 「每个元素出现 $k$ 次、只有一个出现一次」这类题的统一解法是按位统计后对 $k$ 取余。$k = 2$ 时它退化成异或，$k = 3$、$k = 5$ 时异或失效，但逐位取余始终成立——记住通解比记住异或技巧更有价值。
  • 把整数拆成独立的二进制位、对每一位单独求解再拼回去，是位运算题的核心分解手法，「位与位之间互不影响」是这套做法成立的前提。
  • 涉及 32 位补码时，符号位不是特例而是普通的第 $31$ 位，按统一规则统计和写回即可；真正要小心的是宿主语言的整型宽度，在 64 位 int 的语言里必须显式收窄。
  • 有「常数空间」进阶要求时，哈希表和排序基本都被判死，应该立刻往「固定几个累加器 / 状态机」方向想。
  • 面试视角：面试官问这道题，最想听到的是你能说清「为什么 136 题的异或在这里失效」。开口先给出 $O(n)$ 时间、$O(n)$ 空间的哈希表版保底，再主动升级到逐位取余，是稳妥的答题节奏；如果被追问「有没有 $O(1)$ 且不跑 32 轮的写法」，可以补充「用 ones、twos 两个变量做模 $3$ 状态机」，即 ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones，但要说明它更难现场推导、逐位版更适合白板。

易错点总结

  • 错误写法：直接把所有元素异或起来。输入 [2, 2, 3, 2] 恰好得到 3，容易让人误以为可行；但输入 [2, 2, 2, 3, 3, 3, 5] 会得到 2 ^ 3 ^ 5 = 4，正确答案是 5。异或的自消周期是 $2$，对三次重复无效。
  • 错误写法：外层只跑到 31 之前（如 i < 31）。输入 [-2, -2, -2, -3] 时符号位没被还原，返回的是一个正数 $2147483645$ 而不是 -3。
  • 错误写法：Go 里用 int 累积 answer。输入 [1, 1, 1, -2147483648] 时 answer |= 1 << 31 得到 $2147483648$，返回正数而不是 -2147483648。
  • 错误写法：取位写成 x & (1 << i) 后直接累加。累加的是 $2^i$ 而不是 $0/1$，cnt % 3 的语义彻底失效，输入 [2, 2, 2, 3] 就会返回错值；要么改成 (x >> i) & 1，要么把结果再除以 $2^i$。
  • 错误写法：忘记 cnt %= 3，直接 answer |= (cnt & 1) << i。这等价于对 $2$ 取余，输入 [2, 2, 2, 3] 第 $1$ 位的 cnt = 4，4 & 1 = 0，答案丢掉这一位，返回 1 而不是 3。
  • 错误写法：用 HashMap 统计每个数的出现次数再找计数为 $1$ 的。结果对，但空间是 $O(n)$，直接违反进阶要求，面试中会被要求重写。
  • 错误写法：先排序再每三个一组比较。同样能过，但时间退化到 $O(n \log n)$，而且分组比较的下标边界（末尾不足三个）很容易写错。
  • 错误写法：把 answer |= cnt << i 写成 answer += cnt << i 并把 cnt 忘了取余。此时累加的是原始计数，[2, 2, 2, 3] 会返回 $2 \times 4 + 1 = 9$ 之类的错值。

相似题目

题目 难度 考察点
137. 只出现一次的数字 II 中等 与本题同题，可直接套用逐位模 $3$
剑指 Offer 56 - II. 数组中数字出现的次数 II 中等 同为模 $3$，但题目保证元素非负，不必处理符号位
136. 只出现一次的数字 简单 重复次数是 $2$，整体异或一行出结果，是本题的退化情形
260. 只出现一次的数字 III 中等 有两个独苗，需先用 x & -x 取异或和的最低位把数组分成两组
剑指 Offer 56 - I. 数组中数字出现的次数 中等 与 260 同题，考的是「按某一位分组后各自异或」这一步
191. 位1的个数 简单 只做单个数的逐位统计，是本题内层循环的最小版本