2016-12-29 9 views
0

Оператор Вопрос заключается в следующем: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, когда точки являются положительными и отрицательными, и один из таких тестов случай упомянут выше

+1

Ну, что 'Double.MIN_VALUE - Double.MIN_VALUE' в Java ? Кстати, есть ли причина, по которой вы используете для этого приоритетную очередь, вместо того, чтобы просто сортировать точки по расстоянию до начала координат и возвращать им первые «k»? –

+0

Я могу обойтись без очереди приоритетов. Затем мне нужно рассчитать расстояние от начала координат для каждой точки, а затем отсортировать расстояния и взять первые k расстояний. Расстояния можно сопоставить с точками, используя hashmap. Я просто думал сохранить память и не принимать хэш-карту. Сложность в обоих сценариях будет O (n logn) – ojas

+0

Я выяснил решение, используя treeMap, хотя – ojas

ответ

1

Для вопроса вы спрашивают, есть проблема вычисления расстояния:

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 = 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 поэтому мы используем его в compareTo способе Comparator определен:

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

 Смежные вопросы

  • Нет связанных вопросов^_^