数组中只出现一次的数字
哪些公司问过
答案要点
- 异或性质:a ^ a = 0,a ^ 0 = a,满足交换律和结合律
- 把所有数依次异或,成对的抵消,剩下的就是只出现一次的数
- 时间 O(n),空间 O(1)
- 其他做法:哈希表计数 O(n) 空间;排序后比较相邻元素 O(n log n)
- 变形:两个单独的数按某一位分组再异或;其他数出现三次时统计每位 1 的个数模 3
易错点
- 用哈希表却被要求常数空间
- 不知道异或的交换律,以为顺序有影响
- 变形题里分组的依据找错
- 忽略数组为空的情况
面试官常见追问
- 如果有两个数只出现一次,怎么找?
- 其他数都出现三次,只有一个数出现一次,怎么找?
- 异或为什么能抵消?
- 用哈希表有什么缺点?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 数组和链表的区别与适用场景173 场
- 经典算法题:最长回文子串、无重复最长子串、最大子数组和141 场
- 合并有序数组与合并区间66 场
- 三数之和:排序加双指针50 场
- 字符串相加(大数加法)20 场
- 字符串匹配:KMP 算法18 场
- 字符串反转的实现与注意事项17 场
- 接雨水问题的三种解法14 场
- 螺旋矩阵遍历14 场
- 两数之和的几种解法12 场