612. K Closest Points

Description

Given some points and an origin point in two-dimensional space, find k points which are nearest to the origin.

Return these points sorted by distance, if they are same in distance, sorted by the x-axis, and if they are same in the x-axis, sorted by y-axis.

Example

Example 1:

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

Output: [[1,1],[2,5],[4,4]]

Example 2:

Input: points = [[0,0],[0,9]], origin = [3, 1], k = 1

Output: [[0,0]]

思路：

基于 PriorityQueue 的方法

PriorityQueue 里从远到近排序。当 PQ 里超过 k 个的时候，就 pop 掉一个。

时间复杂度 O(nlogk)

代码：