Contents

# Problem

We have a list of `points` on the plane. Find the `K` closest points to the origin `(0, 0)`.

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

## example 1

 ``````1 2 3 4 5 6 7 `````` ``````Input: points = [[1,3],[-2,2]], K = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]]. ``````

## example 2

 ``````1 2 3 `````` ``````Input: points = [[3,3],[5,-1],[-2,4]], K = 2 Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.) ``````

## Constraints

• 1 <= `K` <= `len(points)` <= 10000
• -10000 < `points[i][0]` < 10000
• -10000 < `points[i][1]` < 10000

# Solution

## Priority queue

 `````` 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 `````` ``````func kClosest(points [][]int, K int) [][]int { res := make(PQ, len(points)) for idx:=range points{ res[idx] = getn(points[idx]) } heap.Init(&res) resa := make([][]int, 0) for i:=0;i

## Merge sort

 `````` 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 `````` ``````func kClosest(points [][]int, K int) [][]int { f := sort(points) return f[:K] } func sort(points [][]int) [][]int{ if len(points) == 1 { return points } if len(points) ==2 { if dist(points[0])>dist(points[1]){ points[0],points[1] = points[1],points[0] } return points } m:= len(points)/2 left:=sort(points[0: m]) right:=sort(points[m:len(points)]) res := make([][]int,0,len(points)) i:=0 j:=0 for i