我试图实现这个算法的更简单版本,但它比二次算法更好.我的想法主要是只用x坐标对点进行排序,并尝试从那里解决它.一旦我按x坐标对点阵列进行排序,我想迭代数组,基本上跳过距离大于我前两点的点.
例如,我的currentminDist = x;
如果我正在观察的两对点的距离> x(仅由其x coord dist),我忽略该点并在数组中移过它.
我有这个想法,但我有点坚持如何实际实现这一点(特别是条件部分).我有一个函数,它根据x坐标返回两点之间的距离.
我很困惑如何实际为我的循环写我的条件因为我想忽略一个点,如果距离恰好太远并仍然填写我的数组,其中将包含每个i的最近点的答案(我是当前点我在看).
任何提示或方向将不胜感激.我对编码算法知之甚少,所以非常令人沮丧.
这是我的代码的一部分：
for (i = 0; i < numofmypoints; i++)
{
for (int j = i + 1; (j < numpofmypoints) && ((inputpoints[j].x - inputpoints[i].x) < currbest); j++ )
{
currdist = Auxilary.distbyX(inputpoints[i],inputpoints[j]);
if (currdist < bestdist)
{
closest[i] = j;
bestdist = currdist;
}
}
}
distbyX是我的函数,只返回两点之间的距离.
谢谢！
最佳答案
使用KD树的快速算法
该算法创建kd树,然后为每个点找到最接近的对.创建kd树是O(n log2n),找到一个点的最近邻居是O(logn).信用必须转到Wikipedia,在一篇文章中解释了如何创建kd树以及如何使用它们来查找最近的邻居.
原文链接：https://www.f2er.com/java/438020.html该算法创建kd树,然后为每个点找到最接近的对.创建kd树是O(n log2n),找到一个点的最近邻居是O(logn).信用必须转到Wikipedia,在一篇文章中解释了如何创建kd树以及如何使用它们来查找最近的邻居.
import java.util.*;
public class Program
{
public static void main(String[] args)
{
List修复问题中的代码
如果你真的不担心复杂性,那么你的代码唯一的问题就是你向前看但不向后看.只需复制内部循环并使j从(i – 1)变为0：
Point[] points = sort(input());
int[] closest = new int[points.length];
for (int i = 0; i < points.length; i++)
{
double bestdist = Double.POSITIVE_INFINITY;
for (int j = i + 1; (j < points.length) && ((points[j].x - points[i].x) < bestdist); j++ )
{
double currdist = dist(points[i],points[j]);
if (currdist < bestdist)
{
closest[i] = j;
bestdist = currdist;
}
}
for (int j = i - 1; (j >= 0) && ((points[i].x - points[j].x) < bestdist); j-- )
{
double currdist = dist(points[i],points[j]);
if (currdist < bestdist)
{
closest[i] = j;
bestdist = currdist;
}
}
}
