二维平面中的 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为正数

现在计算Point # 0和Point # 1之间的距离，Point # 0和[=之间的距离时，欧氏距离d = Math.sqrt(((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y)));returnInfinity 20=], 因为:

点#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 表示 "Both Points are equal"，而 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 class 没有这样的方法（如果你 here 你可以）。
因为如果a > b那么sqrt(a) > sqrt(b)，它是成比例的，所以不需要应用平方根函数就可以得到这个值。

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

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

二维平面中的 K 最近邻

K nearest neighbour in a 2d plane

java

algorithm

heap

priority-queue