给定屏幕与2D对象数组,求中心螺旋排序前k个对象的最快算法
最优算法方案:基于极角+距离的快速选择
- 核心逻辑:螺旋顺序的本质是先按点与屏幕中心的极角(匹配图示的螺旋起始方向,比如从右侧开始逆时针排序)划分优先级,极角相同的点则按到中心的距离由近到远排序。要输出前k个点,无需对所有n个点全量排序。
- 具体步骤:
- 计算屏幕中心坐标
(cx, cy),对每个点计算两个参数:用atan2(y - cy, x - cx)得到极角(可调整角度区间以匹配螺旋的起始与旋转方向),以及到中心的平方距离(避免开方运算,提升效率)。 - 定义排序优先级:优先按极角(符合螺旋的角度顺序)排序,极角一致时按平方距离从小到大排序。
- 采用快速选择算法,基于上述优先级规则直接筛选出前k个优先级最高的点,平均时间复杂度为O(n),远优于全排序的O(n logn)。
- 对选出的k个点按规则做局部排序后输出即可。
- 计算屏幕中心坐标
- 对比原思路的优势:原思路需要对所有点全排序,当k远小于n时,快速选择能避免大量无意义的排序计算,效率提升明显。
内容的提问来源于stack exchange,提问作者HamsterGamer
相关产品推荐
相关产品推荐

