gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:15:40 24 4
gpt4 key购买 nike

问题陈述如下:

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

最佳答案

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

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 = Infinitytrue ,因此 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);
}

关于java - 二维平面中的 K 最近邻,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41386490/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com