大廠面試真題詳解：K個最近的點

給定一些 points 和一個 origin，從 points 中找到 k 個離 origin 最近的點。按照距離由小到大傳回。如果兩個點有相同距離，則按照x值來排序；若x值也相同，就再按照y值排序。

線上評測位址：

領扣題庫官網 例1:

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

例2:

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

題解

使用 Heapify 的方法

heapify 時間複雜度 O(n) 然後 pop k 個點出來，時間複雜度 klogn 總共的時間複雜度 O(n+klogn)

如果 n >> k 的話，這種方法的時間複雜度是很優秀的。

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);
        return top;
    }
    
    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);
    }
}           

更多題解參考：

九章官網solution