找出平面上落在给定圆内的所有点
哪些公司问过
答案要点
- 暴力法:比较距离平方与r²,O(n)
- 多次查询需建空间索引
- 网格法:只检查与圆外接正方形相交的格子,再精确判断
- KD树范围查询,包围盒与圆不相交即剪枝
- 动态数据可用R树或四叉树,GeoHash可转为一维前缀查询
易错点
- 用开方计算距离,增加不必要的开销和精度问题
- 网格法只查圆心所在格子,漏掉跨格的点
- 只用外接正方形判断,没有再精确判断距离
面试官常见追问
- 为什么倒排索引不适合这个问题?
- 网格边长怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。