咨询动态更新起点的点集按近远排序的O(nlogn)实现算法
算法选型需求
- 待处理点集合:
p1(10,-4)、p2(8,3)、p3(6,-4)、p4(5,1) - 初始计算基准:
p0(7,0) - 遍历规则:每选定一个点加入输出序列后,下一轮的距离计算基准自动切换为刚选中的点,从剩余未选中的点中选出距离最近的点作为下一个序列元素,直到所有点全部被遍历完成
- 执行逻辑验证:
按规则执行可得到预期输出序列p4, p2, p1, p3,对应步骤为:- 首轮以p0为基准,计算所有待选点到p0的距离,最近的p4作为序列首项,基准更新为p4
- 以p4为基准,计算剩余未选点到p4的距离,最近的p2作为序列第二项,基准更新为p2
- 以p2为基准,计算剩余未选点到p2的距离,最近的p1作为序列第三项,基准更新为p1
- 剩余的最后一个点p3作为序列末项
- 算法性能要求:时间复杂度达到O(nlogn)
内容的提问来源于stack exchange,提问作者Osmion
相关产品推荐
相关产品推荐

