题目简述数组里每个数都出现 3 次只有一个数出现 1 次。找出这个单数。要求O(n) 时间O(1) 空间不能用哈希表当计数用。对比 136出现2次 → 直接异或本题是“出现3次”异或不够用了需要模3状态机。核心思路两位状态机位运算最推荐把每个数的每一位单独看统计出现次数对 3 取模结果只能是“0 / 1 / 2”。用两个变量模拟这个“模3计数器”“one”该位出现次数 ≡ 1 (mod 3)“two”该位出现次数 ≡ 2 (mod 3)状态转移遇到新数“x”one (one ^ x) ~two # 有two时不保留onetwo (two ^ x) ~one # 有one时不保留two效果第1次见→one1第2次见→one0,two1第3次见→全清0。完美循环。最终“one” 就是只出现一次的那个数。✅ Python3 实现LeetCode 直接提交from typing import Listclass Solution:def singleNumber(self, nums: List[int]) - int:one 0two 0for x in nums:one (one ^ x) ~twotwo (two ^ x) ~onereturn onePython 整数不限位数直接返回“one” 即可LeetCode 判题通过 ✅ 备选逐位统计法更好理解对 32 位每一位统计 1 的个数模 3 取余后拼回整数最后处理负数补码。class Solution:def singleNumber(self, nums: List[int]) - int:res 0for i in range(32):cnt 0mask 1 ifor x in nums:if x mask:cnt 1if cnt % 3:res | mask# 转回 32 位有符号整数处理负数if res (1 31):res - (1 32)return res复杂度维度 状态机版 逐位版时间 O(n) O(32n) ≈ O(n)空间 O(1) O(1)136 vs 137 对照记忆题目 出现次数 解法 核心运算136 Single Number 2次 1个单次 异或累加“a ^ a 0”137 Single Number II 3次 1个单次 模3状态机“one/two” 双变量260 Single Number III 2次 2个单次 异或分组 按最低不同位拆分状态机直观例子某一位初始 one0 two0见第1次: one1 two0见第2次: one0 two1见第3次: one0 two0 ← 归零像模3计数器要不要我把 137 推广到“出现 k 次”的通解思路或者顺手把 260两个单数的 Python 版也补上做套题整理
