找出数组中两个只出现一次的数字
哪些公司问过
答案要点
- 全体异或后,成对的数抵消,得到两个目标数的异或值 x,且 x 不为 0
- 取 x 中任意一个为 1 的位(常用 x & -x 取最低位),两个目标数在该位不同
- 按该位是 0 还是 1 分组,相同的数必然同组,每组各剩一个目标数
- 两组分别异或得到结果,时间 O(n),空间 O(1)
易错点
- 按 x 的某一位分组时取到了为 0 的位,导致两个目标数落在同一组
- C/C++ 对有符号整数最小值直接取负,产生有符号溢出
- 误以为分组要把数组真的拆成两个数组,其实一遍遍历加一个累加变量即可
面试官常见追问
- 如果只有一个数出现一次、其余出现两次呢?
- 如果其余数出现三次,只有一个数出现一次怎么做?
- 为什么 x & -x 能取到最低位的 1?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场