973. K Closest Points
https://leetcode.com/problems/k-closest-points-to-origin/
solution
heap
最小的k个
大顶堆: 堆长度超过k之后, pop出去一个大的, 但python只有小顶堆只能pop出去小的,因此取负数。这样python小顶堆里留下了k个最大的,但其实是最小
小顶堆: 所有元素入堆之后, pop出k个小的
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
heap = []
for i, point in enumerate(points):
dis = self._distance(point, (0, 0))
# heappush: inserting an item to a heap of size k take O(logK) time
heapq.heappush(heap, (-dis, i)) # 这里也可以换成(-dis, x, y)入堆
if len(heap) > k:
heapq.heappop(heap)
res = []
for dis, i in heap:
res.append(points[i])
return res
def _distance(self, point1, point2):
x1, y1 = point1
x2, y2 = point2
return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
时间复杂度:O(nlogk) 空间复杂度:O(k)
quick select
时间复杂度:O() 空间复杂度:O()
Last updated