两个数列中一个多出一个数,找出这个数
哪些公司问过
答案要点
- 所有元素异或,成对的数抵消为 0,剩下的就是多出的数
- 依据:a⊕a=0,a⊕0=a,满足交换律和结合律
- 异或法时间 O(n)、空间 O(1),不受顺序和重复值影响
- 求和相减也可行,但需注意溢出
- 哈希计数空间 O(n),可推广到多个差异元素或非整数
易错点
- 只说排序后逐个比较,复杂度 O(n log n) 不是最优
- 用求和法不考虑整数溢出
- 误以为异或法要求两个数列有序
面试官常见追问
- 如果多出两个数怎么找?
- 异或法为什么不适用于浮点数?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。