973. K Closest Points to Origin
MaxHeap. 题解摘抄： We can maintain a max-heap with size K. Then for each point, we add it to the heap. Once the size of the heap is greater than K, we are supposed to extract one from the max heap to ensure the size of the heap is always K. Thus, the max heap is always maintain top K smallest elements from the first one to crruent one. Once the size of the heap is over its maximum capacity, it will exclude the maximum element in it, since it can not be the proper candidate anymore.
Time complexity: O(NlogK)
class Solution {
public int[][] kClosest(int[][] points, int K) {
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(K, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
int d1 = o1[0] * o1[0] + o1[1] * o1[1];
int d2 = o2[0] * o2[0] + o2[1] * o2[1];
return d2 - d1; // max heap
}
});
for (int[] point : points) {
maxHeap.offer(point);
if (maxHeap.size() > K) {
maxHeap.poll();
}
}
int[][] res = new int[K][2];
for (int i = K - 1; i >= 0; i--) {
res[i] = maxHeap.poll();
}
return res;
}
}