java - 最近点 - 进近缺陷

Question

我正在解决来自 here 的最近点问题

问题陈述:

We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array.

INPUT : Input will be two arrays X and Y, X[] stores x coordinates and Y[] stores y coordinates.

OUTPUT : Smallest distance.

我的算法:

注意:方法仅适用于正坐标。

1. 找出从 (0,0) 开始的所有坐标之间的距离，并将其存储在距离数组中。

2. 对上一步计算的距离数组进行排序。

3. 通过计算距离数组中两个连续值之间的差值来找到最小距离。

代码:

public class ClosestPoint {
    int x[]={2,12,40,5,12,3},y[]={3,30,50,1,10,4}; // x and y coordinates
    float distance[] = {0,0,0,0,0,0}; // distance
    
    void calculateDis(){
        for(int i=0;i<x.length;i++){
            int dis=(x[i]*x[i] + y[i]*y[i]);
            distance[i]= (float)Math.sqrt(dis);
        }
    }
    
    float findClosest() {
        float closest = Float.MAX_VALUE;
        for(int i=0;i<distance.length-1;i++) {
            float pairDis= distance[i+1]-distance[i];
            if(closest>pairDis) {
                closest =pairDis;
            }
        }
        return closest;
    }
    public static void main(String arg[]) {
        ClosestPoint p =new ClosestPoint();
        p.calculateDis(); // calculate distance from 0,0.
        Arrays.sort(p.distance);
        System.out.println(p.findClosest());
    }
}

正确答案:1.4

我的答案:0.099

我没有得到正确答案。有人可以指出我方法中的缺陷吗。

谢谢。

Answer 1

实际问题出在逻辑上。您正在计算与原点的距离并进行比较。这可能会导致错误的答案。

考虑点 (3,4) 和 (4,3) 的示例。两者与原点的距离相同 - 5。所以根据你的逻辑，你对距离进行排序并取最小连续距离，所以这里你的算法将返回 0 (因为排序后数组将是 5.0 ，5.0)但实际答案是 .