973_最接近原点的_K_个点

类型：堆

• 973. 最接近原点的 K 个点 💛

  https://leetcode-cn.com/problems/k-closest-points-to-origin/

  ❓ 我们有一个由平面上的点组成的列表 points。请从中找出 K 个距离原点 (0, 0) 最近的点。

  💡 堆

  这题跟「面试题 17.14. 最小K个数」是一样的。

  class Solution:
      def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
          if not points or k <= 0:
              return []
          h = []
          for i in range(len(points)):
              p = points[i]
              dis = p[0] ** 2 + p[1] ** 2
              if len(h) < k or dis < -h[0][0]:
                  heapq.heappush(h, (-dis, i))
              if len(h) > k:
                  heapq.heappop(h)
          ans = []
          for item in h:
              ans.append(points[item[1]])
          return ans