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()