在2D平面K近邻

查找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时的点是积极的和消极的，一个这样的试验情况进行了

来源

2016-12-29 ojas

那么，什么是'Double.MIN_VALUE - Double.MIN_VALUE'在Java中？顺便说一下，是否有一个原因，你为什么使用优先级队列，而不是按距离原点排序点并返回它们的第一个“k”？ – 2016-12-29 20:11:37

我可以没有优先级队列。然后，我必须计算每个点与原点之间的距离，然后对距离进行排序并获取前k个距离。距离可以使用散列图映射到点。我只是想保存内存，而不是采用hashmap。这两种情况下的复杂性将是O（n logn） – ojas

我想通过treeMap解决方案虽然 – ojas

提到的问题，您都在问，有一个问题计算距离：

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 # 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类没有这样的方法（如果你可以使用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); 
}

来源

2016-12-29 22:05:55

在2D平面K近邻

回答

相关问题