圆形范围内查找怪物:空间索引优化
哪些公司问过
答案要点
- 暴力遍历每次 O(n),优化思路是空间索引先粗筛候选,再精确判断距离
- 均匀网格:按固定边长分格,每格存怪物列表,移动跨格时 O(1) 维护
- 查询只遍历与圆的外接正方形相交的格子,用 dx²+dy²≤r² 比较避免开方
- 格子大小与查询半径同量级;分布不均用四叉树,静态数据可用 k-d 树
- 复杂度约为覆盖格子数加候选数,远小于 n,适合频繁查询与频繁移动
易错点
- 只查圆心所在的一个格子,漏掉半径覆盖到的相邻格子
- 粗筛后不做精确距离判断,把正方形角落里的怪物也算进圆内
- 用 sqrt 计算距离,既慢又引入浮点误差,比较平方即可
面试官常见追问
- 格子大小怎么选?
- 怪物在不断移动,索引怎么维护?
- 怪物分布非常不均匀怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。