1439_有序矩阵中的第_k_个最小数组和

类型：堆

• 1439. 有序矩阵中的第 k 个最小数组和 ❤️

  https://leetcode-cn.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/

  参考：力扣加加

  ❓ 给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。

  💡 堆

  这道题的含义其实就是让你从矩阵的每一行选取一个数，得到和第 k 小的。

  显然可以用堆来解决，我们要保证的是在弹出堆顶元素的时候，不存在比它小却尚未入堆的元素。

  class Solution:
      def kthSmallest(self, mat: List[List[int]], k: int) -> int:
          cur = (sum([row[0] for row in mat]), tuple([0] * len(mat)))
          heap = [cur]
          seen = set(cur)
          for _ in range(k):
  						# poses 是当前指针情况
              theSum, poses = heapq.heappop(heap)
  						# 尝试将每个指针向后移一位
              for i, pos in enumerate(poses):
                  if pos < len(mat[0]) - 1:
                      posesArr = list(poses)
                      posesArr[i] = pos + 1
                      posesTuple = tuple(posesArr)
                      if posesTuple not in seen:
                          seen.add(posesTuple)
                          heapq.heappush(heap, (sum(mat[i][posesTuple[i]] for i in range(len(mat))), posesTuple))
  
          return theSum