LeetCode 973. 最接近原点的 K 个点 - Python
原题链接
中等
作者:
小聂同学
,
2023-10-09 01:50:05
,
所有人可见
,
阅读 78
from math import sqrt
from heapq import heappop, heappush
class Solution:
'''
Main Idea - Use Heap
Use max heap to store tuple (distance, index)
Time Complexity: O(nlogk)
Space Complexity: O(k)
'''
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
max_heap = []
for idx, point in enumerate(points):
x,y = point
distance = sqrt(x**2 + y**2)
heappush(max_heap, (-distance, idx))
if len(max_heap) > k:
heappop(max_heap)
return [points[idx] for distance, idx in max_heap]