每日一道Leetcode - 378. 有序矩阵中第 K 小的元素【堆｜归并排序】_leetcode 378 python 堆

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        # 存储每行第一个值，以及其对应下标
        queue = [(matrix[i][0],i,0) for i in range(n)]
        # 创建堆，直接一个列表所有元素入堆
        heapq.heapify(queue)

        res = []
        for i in range(k):
            num,x,y = heapq.heappop(queue)
            res.append(num)
            if y!=n-1:
                # 没有达到边界的情况
                # 将当前弹出元素的右边的元素继续入栈
                heapq.heappush(queue,(matrix[x][y+1],x,y+1))
        return res[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17