1到100中缺失了一个数,如何快速找到?推广到1到N呢?
哪些公司问过
答案要点
- 求和法:5050 减去实际和,推广为 N(N+1)/2 减去数组和
- 异或法:1..N 与数组元素异或,成对抵消,无溢出
- 时间 O(n),空间 O(1)
- N 大时求和用 64 位或边加边减防溢出
- 有序数组用二分 O(log n);海量数据用位图或分段计数
易错点
- 求和用 int 导致溢出
- 有序数组仍然线性扫描,没想到二分
- 二分时下标与值的偏移关系写错
面试官常见追问
- 如果 1 到 N 中缺了两个数怎么办?
- 如果有 40 亿个整数,内存只有 1GB,怎么找一个没出现的数?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。