java - 二维平面中的 K 最近邻

Question

问题陈述如下:

Find the K closest points to the origin in a 2D plane, given an array containing N points.The output must be in non decreasing order.

解决方案:我已经使用比较器和优先级队列解决了这个问题，我的代码如下所示:

class Point {
    double x;
    double y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

public class KClosestPoints {
    public Point[] getKNearestPoints(Point[] points, int k) {
        if (k == 0 || points.length == 0) {
            return new Point[0];
        }
        Point[] rValue = new Point[k];
        int index = k - 1;
        if (points.length < k) {
            index = points.length - 1;
        }
        final Point org = new Point(0, 0);
        PriorityQueue<Point> pq = new PriorityQueue<Point>(k,
                new Comparator<Point>() {
                    @Override
                    public int compare(Point o1, Point o2) {
                    Double d2 = getDistance(o2, org);
                    Double d1 = getDistance(o1, org);
                    if (d2 > d1) {
                        return 1;
                    } else if (d2 < d1) {
                        return -1;
                    } else
                        return 0;
                }
                });
        for (int i = 0; i < points.length; i++) {
            pq.offer(points[i]);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        while (!pq.isEmpty()) {
            rValue[index] = pq.poll();
            index--;
        }
        return rValue;
    }

    private static double getDistance(Point a, Point b) {
        return Math.sqrt(((a.x - b.x) * (a.x - b.x))
                + ((a.y - b.y) * (a.y - b.y)));
    }

我的代码适用于我使用过的所有测试用例，除了这个:

test6[0] = new Point(Double.MIN_VALUE, Double.MAX_VALUE);
test6[1] = new Point(Double.MIN_VALUE, Double.MIN_VALUE);
test6[2] = new Point(Double.MAX_VALUE, Double.MAX_VALUE);
getKNearestPoints(test6, 2);

答案应该是 test6[0] 和 test6[1]，而这段代码给出的答案是 test6[0] 和 test6[2]。帮助我找到问题所在。

编辑:后来我注意到它在所有 k = 2 的测试用例中给出了错误的答案，当点为正和负时，上面提到了一个这样的测试用例

Answer 1

你问的问题，计算距离有问题:

Point # 0 = (0, 0)
Point # 1 = (Double.MIN_VALUE, Double.MAX_VALUE) -> (4.9E-324, 1.7E308)
Point # 2 = (Double.MIN_VALUE, Double.MIN_VALUE) -> (4.9E-324, 4.9E-324)
Point # 3 = (Double.MAX_VALUE, Double.MAX_VALUE) -> (1.7E308, 1.7E308)

注意: Double.MIN_VALUE是正数。

现在欧式距离d = Math.sqrt(((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y)));返回 Infinity在计算 Point # 0 之间的距离时和 Point # 1 , 和 Point # 0 之间和 Point # 3 ，因为:

第 1 点

(a.x - b.x) * (a.x - b.x) = (1.7E308 - 0) * (1.7E308 - 0) = 1.7E308 * 1.7E308 = Infinity
Math.sqrt(Infinity + Infinity) = Infinity;

得到Point # 1的距离后和 Point # 0 ( Infinity ), 然后与 Point # 3 的距离进行比较和 Point # 0 (还有 Infinity )然后 Infinity = Infinity是true ，因此 Comparator表示“两点相等”，PriorityQueue不要随意订购。

对于 Double.MAX_VALUE 的操作你不能使用 Double ，而是使用 BigDecimal :

private BigDecimal getDistance(Point a, Point b) {
    BigDecimal dx = BigDecimal.valueOf(a.x - b.x);
    BigDecimal dy = BigDecimal.valueOf(a.y - b.y);
    BigDecimal distance = dx.pow(2).add(dy.pow(2));
    return distance;
}

为什么我们不用平方根来计算实际距离？因为:

• BigDecimal 类没有这样的方法(如果你 which here 你可以)。
• 因为如果a > b然后sqrt(a) > sqrt(b) ，它是正比的，所以不用平方根函数就可以得到这个值。

利用BigDecimal , 它实现了自己的 Comparator所以我们在 compareTo 中使用它Comparator 的方法定义:

@Override
public int compare(Point o1, Point o2) {
    BigDecimal d1 = getDistance(o1);
    BigDecimal d2 = getDistance(o2);
    return d1.compareTo(d2);
}