k_closest_points_to_origin
1from heapq import heapify, heappop 2 3 4# @leet start 5class Solution: 6 def kClosest(self, points: list[list[int]], k: int) -> list[tuple[int]]: 7 """ 8 The best solution involves sorting via quickselect in $O(n)$ time. 9 This solultion works in $O(n{}\log{}k)$ time and uses a min-heap. 10 The heap pops off points by closest distance and saves them a list, 11 and returns the list. 12 """ 13 distances = [(x**2 + y**2, (x, y)) for x, y in points] 14 heapify(distances) 15 return [heappop(distances)[1] for _ in range(k)] 16 17 18# @leet end 19sol = Solution() 20 21 22def test(): 23 assert sol.kClosest([[1, 3], [-2, 2]], 1) == [(-2, -2)] 24 assert sol.kClosest([[3, 3], [5, -1], [-2, 4]], 2) == [(3, 3), (-2, 4)]
class
Solution:
6class Solution: 7 def kClosest(self, points: list[list[int]], k: int) -> list[tuple[int]]: 8 """ 9 The best solution involves sorting via quickselect in $O(n)$ time. 10 This solultion works in $O(n{}\log{}k)$ time and uses a min-heap. 11 The heap pops off points by closest distance and saves them a list, 12 and returns the list. 13 """ 14 distances = [(x**2 + y**2, (x, y)) for x, y in points] 15 heapify(distances) 16 return [heappop(distances)[1] for _ in range(k)]
def
kClosest(self, points: list[list[int]], k: int) -> list[tuple[int]]:
7 def kClosest(self, points: list[list[int]], k: int) -> list[tuple[int]]: 8 """ 9 The best solution involves sorting via quickselect in $O(n)$ time. 10 This solultion works in $O(n{}\log{}k)$ time and uses a min-heap. 11 The heap pops off points by closest distance and saves them a list, 12 and returns the list. 13 """ 14 distances = [(x**2 + y**2, (x, y)) for x, y in points] 15 heapify(distances) 16 return [heappop(distances)[1] for _ in range(k)]
The best solution involves sorting via quickselect in $O(n)$ time. This solultion works in $O(n{}\log{}k)$ time and uses a min-heap. The heap pops off points by closest distance and saves them a list, and returns the list.
sol =
<Solution object>
def
test():