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

二维平面中的K个最近邻

  •  0
  • ojas  · 技术社区  · 8 年前

    问题陈述如下:

    在给定阵列的情况下,在二维平面中找到离原点最近的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 回复  |  直到 8 年前
        1
  •  1
  •   Community CDub    8 年前

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

    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);
    }