java – 最近的一对点算法
发布时间:2020-12-14 19:18:11 所属栏目:Java 来源:网络整理
导读:我试图实现这个算法的更简单版本,但它比二次算法更好.我的想法主要是只用x坐标对点进行排序,并尝试从那里解决它.一旦我按x坐标对点阵列进行排序,我想迭代数组,基本上跳过距离大于我前两点的点. 例如,我的currentminDist = x; 如果我正在观察的两对点的距离 x
我试图实现这个算法的更简单版本,但它比二次算法更好.我的想法主要是只用x坐标对点进行排序,并尝试从那里解决它.一旦我按x坐标对点阵列进行排序,我想迭代数组,基本上跳过距离大于我前两点的点. 例如,我的currentminDist = x; 如果我正在观察的两对点的距离> x(仅由其x coord dist),我忽略该点并在数组中移过它. 我有这个想法,但我有点坚持如何实际实现这一点(特别是条件部分).我有一个函数,它根据x坐标返回两点之间的距离. 我很困惑如何实际为我的循环写我的条件因为我想忽略一个点,如果距离恰好太远并仍然填写我的数组,其中将包含每个i的最近点的答案(我是当前点我在看). 任何提示或方向将不胜感激.我对编码算法知之甚少,所以非常令人沮丧. 这是我的代码的一部分:
distbyX是我的函数,只返回两点之间的距离. 谢谢! 最佳答案
使用KD树的快速算法
该算法创建kd树,然后为每个点找到最接近的对.创建kd树是O(n log2n),找到一个点的最近邻居是O(logn).信用必须转到Wikipedia,在一篇文章中解释了如何创建kd树以及如何使用它们来查找最近的邻居.
修复问题中的代码
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |