You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

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

. 2 min read

【Min-Heap】

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

(这里,平面上两点之间的距离是欧几里德距离。)

你可以按任何顺序返回答案。除了点坐标的顺序之外,答案确保是唯一的。

Example:

示例 1:

输入:points = [[1,3],[-2,2]], K = 1
输出:[[-2,2]]
解释: 
(1, 3) 和原点之间的距离为 sqrt(10),
(-2, 2) 和原点之间的距离为 sqrt(8),
由于 sqrt(8) < sqrt(10),(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点,所以答案就是 [[-2,2]]。

示例 2:

输入:points = [[3,3],[5,-1],[-2,4]], K = 2
输出:[[3,3],[-2,4]]
(答案 [[-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++) {
      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;
  }
}

转换后加入优先队列,只需一遍O(n+k),但是调用原装库费时,自己写(array-based min-heap)的话会更快一些。

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];
    }
}

先转换为距离,再存储+遍历 O(n)

Notes