# lc973. K Closest Points to Origin

Contents

Given an array of `points` where `points[i] = [xi, yi]` represents a point on the X-Y plane and an integer `k`, return the `k` closest points to the origin `(0, 0)`.

The distance between two points on the X-Y plane is the Euclidean distance (i.e., `√(x1 - x2)2 + (y1 - y2)2`).

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]] Explanation: The answer [[-2,4],[3,3]] would also be accepted. ``````

Constraints:

• `1 <= k <= points.length <= 104`
• `-104 < xi, yi < 104`
###### 解题思路：

 `````` 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(object): def kClosest(self, points, k): """ :type points: List[List[int]] :type k: int :rtype: List[List[int]] """ def calDist(points): return [(x,x[0]*x[0]+x[1]*x[1]) for x in points] def quickSort(lists,i,j): if i >= j: return list pivot = lists[i] low = i high = j while i < j: while i < j and lists[j][1] >= pivot[1]: j -= 1 lists[i]=lists[j] while i < j and lists[i][1] <=pivot[1]: i += 1 lists[j]=lists[i] lists[j] = pivot quickSort(lists,low,i-1) quickSort(lists,i+1,high) return lists _points=calDist(points) _points=quickSort(_points,0,len(_points)-1) return [_points[idx][0] for idx in range(k)] ``````

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 `````` ``````import heapq class Solution(object): def kClosest(self, points, k): """ :type points: List[List[int]] :type k: int :rtype: List[List[int]] """ def dist(point): return (-(point[0]**2+point[1]**2),point) h=[] for point in points: if len(h)