You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

给定屏幕与2D对象数组,求中心螺旋排序前k个对象的最快算法

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

内容的提问来源于stack exchange,提问作者HamsterGamer

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.07.08 14:10:04