只出现一次的数字(其余每个出现 k 次)
哪些公司问过
答案要点
- k 为偶数时,全体异或即可得到只出现一次的数
- k 为奇数时按位统计每一位上 1 的个数,对 k 取余,余数非零的位属于目标数
- 按位统计对任意 k 成立,时间 O(32n),空间 O(1)
- k 为 3 时可用 ones、twos 两个变量的状态机写法,一次遍历
- 不限空间时用哈希表计数,空间 O(n)
易错点
- k 为奇数时仍然直接异或
- 只统计到 31 位,漏掉符号位导致负数结果错误
- 把题目条件误读为其他数出现次数不固定
面试官常见追问
- 如果有两个数只出现一次,其余出现两次呢?
- 按位统计时负数怎么处理?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。