只出现一次的数字(LeetCode 136/137)
哪些公司问过
腾讯1地平线机器人1
答案要点
- 异或性质:a^a=0、a^0=a,满足交换律与结合律,成对的数相互抵消
- 其余出现 3 次:逐位统计 1 的个数对 3 取模,拼出结果
- 状态机解法:ones = (ones ^ x) & ~twos,twos = (twos ^ x) & ~ones
- 复杂度均为 O(n) 时间、O(1) 空间
- Python 中需处理符号位,结果超过 2^31-1 时减去 2^32
易错点
- 对出现 3 次的情况仍然直接异或
- 按位统计时忽略负数的符号位
- ones 和 twos 的更新顺序写反
面试官常见追问
- 若其余数出现 2 次,是否有更优方法?
- 如果有两个数只出现一次怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。