解
第一步，万年不变的查错。如果给的array是null或空，直接return 0
public Point[] kClosest(Point[] points, Point origin, int k) {
Point[] result = new Point[k];
if (points == null || points.length == 0) {
return result;
}
...
}
只要见到要找k个最x的，我觉得基本上就是PriorityQueue了。这个题也不例外。根据题意，需要自己写一个comparator。因为是找k个最近的，也就是最小的，所以需要MaxHeap。因为最大的那个就是第k个最小的。所有比它大的都肯定不是前k个最小的。而有小的加进来之后，总共就有k+1个了，那么就要poll掉当前最大的一个。所以MaxHeap在这种情况下是最好的。而降序的comparator实际上就是反过来比（只需要记得默认是升序的就行，反过来的升序，就是降序了）。
Queue<Point> distance = new PriorityQueue<>((a, b) -> {
int diff = Double.compare(getDistance(b, origin), getDistance(a, origin));
if (diff == 0) {
diff = b.x - a.x;
}
if (diff == 0) {
diff = b.y - a.y;
}
return diff;
});
这里用到了getDistance来计算两点之间的距离。公式记不住也不要紧吧，毕竟面试不是考数学的，问一下就行。这里有一个小优化我没有做。因为所有坐标都是正数，所以两点之间的距离必定大于一，在我们不需要知道具体的距离，只需要知道谁大谁小的时候，不需要开平方根了，因为given a > 1 and b > 1, if a > b then a^2 > b^2。不过这个优化太小，如果面试时直接给出这样的优化，面试官肯定瞬间明白你做过这道题。这种小优化不如留到最后，都做完了，再看一遍，再说也不迟。不优化是正常思路。
private 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));
}
然后就是把array里面的点放到PriorityQueue里面了。这个地方其实可以peek一下做对比，如果大于peek的点，就不add。不过这样的话，comparator的逻辑就要写到外面，或者存下来。直接加进去，然后看有没有超过k个，超过了就poll掉最大的，也可以。不算最优，但好在简练。
for (Point point : points) {
distance.add(point);
if (distance.size() > k) {
distance.poll();
}
}
最后，因为是MaxHeap，里面出来的是降序的，题目要求返回升序的，所以倒着存放poll出来的点就可以了。
for (int i = k - 1; i >= 0; i--) {
result[i] = distance.poll();
}
return result;
完整的code
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
/*
* @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) {
Point[] result = new Point[k];
if (points == null || points.length == 0) {
return result;
}
Queue<Point> distance = new PriorityQueue<>((a, b) -> {
int diff = Double.compare(getDistance(b, origin), getDistance(a, origin));
if (diff == 0) {
diff = b.x - a.x;
}
if (diff == 0) {
diff = b.y - a.y;
}
return diff;
});
for (Point point : points) {
distance.add(point);
if (distance.size() > k) {
distance.poll();
}
}
for (int i = k - 1; i >= 0; i--) {
result[i] = distance.poll();
}
return result;
}
private 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));
}
}
分析
时间复杂度
生成size为k的PriorityQueue，是O(k)。然后k后面每个数，insert要log(k)，所以是O((n - k) * logk)。最后取出来是O(klogk)。所以答案是O(k + (n-k)*logk+klogk) = O(k + nlogk) = O(nlogk)。
空间复杂度
用了一个size为k的queue，所以是O(k)。
感觉这道题最难的地方是分析时间复杂度了吧。解题真的不难，逻辑很简单，只要会用PriorityQueue就可以了。
网友评论