给定一些 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);     } }