Оператор Вопрос заключается в следующем:K ближайшего соседа в 2d плоскости
Найти на K ближайших точек в начале координат в 2D плоскости, учитывая массив , содержащий N выход points.The должен быть не по убыванию.
Решение: Я решил это с помощью компаратора и приоритета очереди и мой код выглядит следующим образом:
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]. Помогите мне найти проблему.
EDIT: Позже я заметил, что это дает неправильный ответ во всех тестовых случаях с к = 2, когда точки являются положительными и отрицательными, и один из таких тестов случай упомянут выше
Ну, что 'Double.MIN_VALUE - Double.MIN_VALUE' в Java ? Кстати, есть ли причина, по которой вы используете для этого приоритетную очередь, вместо того, чтобы просто сортировать точки по расстоянию до начала координат и возвращать им первые «k»? –
Я могу обойтись без очереди приоритетов. Затем мне нужно рассчитать расстояние от начала координат для каждой точки, а затем отсортировать расстояния и взять первые k расстояний. Расстояния можно сопоставить с точками, используя hashmap. Я просто думал сохранить память и не принимать хэш-карту. Сложность в обоих сценариях будет O (n logn) – ojas
Я выяснил решение, используя treeMap, хотя – ojas