代码之家 › 专栏 › 技术社区 › ojas

二维平面中的K个最近邻

priority-queue heap algorithm java

0

ojas · 技术社区 · 9 年前

问题陈述如下:

在给定阵列的情况下,在二维平面中找到离原点最近的K个点包含N个点。输出必须为非递减顺序。

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

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的测试用例中,当点为正和负时,它给出了错误的答案,上面提到了一个这样的测试用例

1 回复 | 直到 9 年前

1

Community Mohan Dere 9 年前

对于您所问的问题,计算距离有一个问题:

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 ,及 点#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;

得到距离 第1点 和 点#0 ( 无穷 ),然后将其与 第3点 和 点#0 (也 无穷 )然后 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类没有这样的方法(如果您 here 你可以)。
因为如果 a > b 然后 sqrt(a) > sqrt(b) ,它是成比例的,所以不应用平方根函数就可以得到这个值。

利用 大十进制 ,它实现了自己的 比较器 所以我们在 compareTo 方法 比较器 定义:

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