-
Notifications
You must be signed in to change notification settings - Fork 59
/
LinkedIn: K Nearest points on a plane
56 lines (41 loc) · 1.56 KB
/
LinkedIn: K Nearest points on a plane
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
LinkedIn: K Nearest points on a plane
Question:
Given a list of points and a central point, find the k nearest points from the central point.
Solution:
Use a max heap. First store the first K points into the heap. Then compare the distance between the current point and the max point. If less than the max value, then poll out the max and add the current point into the heap.
Code (Java):
public class Solution {
public List<Point> findKNearestPoints(List<Point> points, Point original, int k) {
List<Point> result = new ArrayList<>();
if (points == null || ponts.size() == 0 || original == null || k <= 0) {
return result;
}
PriorityQueue<Point> pq = new PriorityQueue<>(k);
for (Point point : points) {
if (pq.size() < k) {
pq.offer(point);
} else {
if (pq.peek().compareTo(point) > 0) {
pq.poll();
pq.offer(point);
}
}
}
result.addAll(pq);
return result;
}
class Point implements Comparable<Point> {
int x, y;
double distance;
public Point (int x, int y, Point original) {
this.x= x;
this.y = y;
// sqrt(x^2 + y^2)
distance = Math.hypot(x - original.x, y - original.y);
}
@Override
public int compareTo(Point that) {
return this.distance.compareTo(that.distance);
}
}
}