第一个我们很容易想到将二维数组展开成一维，然后直接进行排序，这里就不多再赘述
思路2，我们可以把此题看作是合并K个有序列表，而他在列上也满足升序排序，所以我们可以通过归并的思想来进行第K小元素查找
from typing import * import heapq class Solution: def kthSmallest(self, matrix: List[List[int]], k: int) -> int: # 思路1 直接取成一维然后排序 # 思路2 利用小根堆进行归并排序 """ 因为矩阵每一行第一个元素，都是其当前行最小的元素 所以我们把他存进小根堆里 因为找第K小元素，实际上我们 按照升序，遍历到第K个即可 我们存进小根堆的是一个三元组(元素值，第一维索引，第二维索引) 每次先弹出栈顶元素，即最小的那个，如果第二维索引没到n-1,表示该行没遍历完 因此读取下一个元素，并存进堆里 如此反复K-1次（因为一开始存了算1次） 栈顶元素就是第K小元素 :param matrix: :param k: :return: """ n = len(matrix) pq = [(matrix[i][0], i, 0) for i in range(n)] heapq.heapify(pq) # print(pq) for i in range(k-1): # print(pq) num, x, y = heapq.heappop(pq) if y != n-1: heapq.heappush(pq, (matrix[x][y+1], x, y+1)) return heapq.heappop(pq)[0]另外我们可以采用二分法，观察到左上角和右下角分别是整个数组的上下界，我们可以通过二分去选取元素，再在这个元素里面，去统计是否是第k小
def kthSmallest2(self, matrix: List[List[int]], k: int) -> int: """ 初始位置在 matrix[n - 1][0]matrix[n−1][0]（即左下角）； 设当前位置为 matrix[i][j]matrix[i][j]。若 matrix[i][j]≤mid， 则将当前所在列的不大于 mid 的数的数量（即 i + 1）累加到答案中，并向右移动，否则向上移动； 不断移动直到走出格子为止。 不妨假设答案为 xx，那么可以知道 l\leq x\leq rl≤x≤r，这样就确定了二分答案的上下界。 每次对于「猜测」的答案 midmid，计算矩阵中有多少数不大于 midmid ： 如果数量不多于 kk，那么说明最终答案 x 不小于 midmid； 如果数量少于 kk，那么说明最终答案 x 大于 midmid。 :param matrix: :param k: :return: """ n = len(matrix) def check(mid): i, j = n-1, 0 num = 0 # 这里取n-1是防止数组越界， while i >= 0 and j < n: if matrix[i][j] <= mid: num += i + 1 j += 1 else: i -= 1 return num >= k left, right = matrix[0][0], matrix[-1][-1] while left < right: mid = (left+right) // 2 if check(mid): right = mid else: left = mid + 1 return left ```