# 大厂面试真题详解：K个最近的点

输入: points = [[4,6],[4,7],[4,4],[2,5],[1,1]], origin = [0, 0], k = 3

输入: points = [[0,0],[0,9]], origin = [3, 1], k = 1

heapify 时间复杂度 O(n) 然后 pop k 个点出来，时间复杂度 klogn 总共的时间复杂度 O(n+klogn)

public class Solution {
private Point origin;
private int size;

/**
* @param points a list of points
* @param origin a point
* @param k an integer
* @return the k closest points
*/
public Point[] kClosest(Point[] points, Point origin, int k) {
if (points == null || points.length == 0) {
return points;
}

this.origin = origin;
heapify(points); // O(n)

Point[] results = new Point[k];
// O(klogn)
for (int i = 0; i < k; i++) {
results[i] = pop(points);
}

return results;
}

private void heapify(Point[] points) {
size = points.length;
for (int i = size / 2; i >= 0; i--) {
siftDown(points, i);
}
}

private void siftDown(Point[] points, int index) {
while (index < size) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int min = index;
if (left < size && compare(points[min], points[left]) > 0) {
min = left;
}
if (right < size && compare(points[min], points[right]) > 0) {
min = right;
}
if (index != min) {
Point temp = points[index];
points[index] = points[min];
points[min] = temp;
index = min;
} else {
break;
}
}
}

private Point pop(Point[] points) {
Point top = points[0];
points[0] = points[size - 1];
this.size--;

siftDown(points, 0);
}

private int compare(Point a, Point b) {
int square = distanceSquare(a, origin) - distanceSquare(b, origin);
if (square != 0) {
return square;
}
if (a.x != b.x) {
return a.x - b.x;
}
return a.y - b.y;
}

private int distanceSquare(Point a, Point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
}

+ 订阅