# 最接近原点的K个点 - K Closest Points to Origin

【Min-Heap】

``````我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。

（这里，平面上两点之间的距离是欧几里德距离。）

``````

### Example:

``````输入：points = [[1,3],[-2,2]], K = 1

(1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，

``````

``````输入：points = [[3,3],[5,-1],[-2,4]], K = 2

（答案 [[-2,4],[3,3]] 也会被接受。）

``````

1. `1 <= K <= points.length <= 10000`
2. `-10000 < points[i][0] < 10000`
3. `-10000 < points[i][1] < 10000`

## Solutions

### Solution 【考点标签】 ( 39ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 `````` ``````class Solution { class Node{ int distance; int index; public Node(int d, int i) { this.distance = d; this.index = i; } } public int[][] kClosest(int[][] points, int K) { int numbers = points.length; Queue priorityQueue = new PriorityQueue(numbers, new Comparator() { public int compare(Node I1, Node I2) { return I1.distance - I2.distance; } }); for (int i = 0; i < numbers; i++) { priorityQueue.add(new Node(points[i][0]*points[i][0] + points[i][1]*points[i][1], i)); } int index = 0; int[][] result = new int[K][2]; for (int i = 0; i < K; i++) { index = priorityQueue.poll().index; result[i][0] = points[index][0]; result[i][1] = points[index][1]; } return result; } } ``````

### Solution ( 22ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 `````` ``````class Solution { public int[][] kClosest(int[][] points, int K) { int[][] ans = new int[K][2]; int[] dist = new int[points.length]; for(int i=0; i< points.length; i++) dist[i] = getDistance(points[i]); Arrays.sort(dist); int distK = dist[K-1]; int t = 0; for(int i=0;i