leetcode378. 有序矩阵中第K小的元素（Python3）_行列皆升序矩阵求第k小数

leetcode378. 有序矩阵中第K小的元素

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。
1
2
3
4
5
6
7
8

提示：

你可以假设 k 的值永远是有效的，1 ≤ k ≤ n^2。

---

方法一：直接排序

思路：

最简单粗暴的方法就是直接将matrix中所有的数据进行排序，然后返回第k小的即可。

排序的方法有很多，我这里直接引入heapq来进行堆排序。

排序的时间复杂度很高，不是最好的方法。

代码：

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        import heapq
        nums = []
        n = len(matrix)
        #将matrix中所有数据加入双向队列中
        for i in range(n
1
2
3
4
5
6