<div>
Given an array of points where points[i] = [x<sub>i</sub>, y<sub>i</sub>] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x<sub>1</sub> - x<sub>2</sub>)<sup>2</sup> + (y<sub>1</sub> - y<sub>2</sub>)<sup>2</sup>).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Example 1:
<pre>Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]]. </pre>
Example 2:
<pre>Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The answer [[-2,4],[3,3]] would also be accepted. </pre>
Constraints:
1 <= k <= points.length <= 10<sup>4</sup>-10<sup>4</sup> < x<sub>i</sub>, y<sub>i</sub> < 10<sup>4</sup>
</div>
算法思路：
最大堆
注意事项：
- 求最小距离用最大堆，距离的相反数入堆
- 与堆顶比较，跟模板一样仍然是大于号
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
if not points or not points[0]:
return 0
heap, res = [], []
for i in range(len(points)):
x, y = points[i][0], points[i][1] # x=-2, y=2
if i < k: # i=1, k=1
heapq.heappush(heap, (-(x * x + y * y), x, y)) # -10, 1, 3
elif -(x * x + y * y) > heap[0][0]: # -8 > -10
heapq.heapreplace(heap, (-(x * x + y * y), x, y)) # -8, -2, -2
while heap:
(dis, x, y) = heapq.heappop(heap) # -8, -2, -2
res.append([x, y])
return res
Java代码：
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
40public int[][] kClosest(int[][] points, int K) {
PriorityQueue<Point> maxHeap = new PriorityQueue<Point>(K,
new Comparator<Point>() {
public int compare(Point o1, Point o2) {
return distance(o2, o1); // descending
}
}
);
for(int i = 0; i < points.length; i++) {
Point p = new Point(points[i][0], points[i][1]);
if(maxHeap.size() < K)
maxHeap.offer(p);
else if(distance(p, maxHeap.peek()) < 0) {
maxHeap.poll();
maxHeap.offer(p);
}
}
int[][] res = new int[K][2];
int j = 0;
while(!maxHeap.isEmpty()) {
Point p = maxHeap.poll();
res[j][0] = p.x;
res[j][1] = p.y;
j++;
}
return res;
}
int distance(Point o1, Point o2) {
return (o1.x * o1.x + o1.y * o1.y) - (o2.x * o2.x + o2.y * o2.y);
}
class Point {
int x;
int y;
Point() { x = 0; y = 0; }
Point(int a, int b) { x = a; y = b; }
}
算法分析：
时间复杂度为O(nlogk)，空间复杂度O(k)
