最近点对问题的分治解法与复杂度
哪些公司问过
答案要点
- 暴力两两比较O(n²)
- 先按x排序,递归求左右两半的最近距离d
- 合并只考虑中线两侧宽为d的带状区域
- 带内按y排序,每个点只需比较常数个(不超过7个)后续点
- 递归中归并维护y序,总复杂度O(n log n)
易错点
- 合并时对带内所有点两两比较,退化为O(n²)
- 每层重新排序却声称是O(n log n)
- 忘记取左右两半最小值作为带宽
面试官常见追问
- 为什么每个点只需要检查常数个点?
- 有没有实际中更简单的做法?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。