You've successfully subscribed to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 973. 最接近原点的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)

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<Node> priorityQueue = new PriorityQueue<Node>(numbers, new Comparator<Node>() {
public int compare(Node I1, Node I2) {
return I1.distance - I2.distance;
}
});

for (int i = 0; i < numbers; 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)

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<points.length;i++){
if(getDistance(points[i]) <= distK)
ans[t++] = points[i];
}
return ans;
}

private static int getDistance(int[] p){
return p[0] * p[0] + p[1] * p[1];
}
}