378. Kth Smallest Element in a Sorted Matrix

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

solution

• 第k小的值，转化为其负数列表中第k大的值。在python最小堆中，最小的数

import heapq

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        if not matrix or not matrix[0]:
            return -1

        heap = []
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):         
                heapq.heappush(heap, matrix[i][j])
        
        for _ in range(k):
            res = heapq.heappop(heap)
        return res

时间复杂度：O() 空间复杂度：O()

• 二分查找

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n: int = len(matrix)
        # 取出矩阵中最小和最大的数字，分别作为二分区间的左右边界
        l: int = matrix[0][0]
        r: int = matrix[n - 1][n - 1]
        # 运用二分找到最小的数 x ，使得矩阵中小于等于 x 的数字个数恰好大于等于 k
        while l <= r:
            # 找到区间中点，计算矩阵中小于等于 mid 的数字个数
            mid: int = l + (r - l) // 2
            count: int = 0
            # 统计每一行中小于等于 mid 的数字个数
            for i in range(n):
                # 由于每一行的数字是递增的，所以可以使用二分（即 upper_bound ），
                # 这样就能在 O(logn) 内求出该行小于等于 mid 的数字个数
                count += bisect.bisect_right(matrix[i], mid)

            if count < k:
                # 如果矩阵中小于 mid 的数字个数小于 k ，
                # 则说明第 k 小的数字在区间右边，
                # 二分区间变为 [mid + 1, r]
                l = mid + 1
            else:
                # 如果矩阵中小于 mid 的数字个数大于等于 k ，
                # 则说明第 k 小的数字在区间左边，
                # 二分区间变为 [l, mid - 1]
                # 
                # （如果恰好 mid 就是所求之数，那么最后区间长度为 1 时，
                #  区间必为 [mid - 1, mid - 1] ，且必有 l = mid - 1 + 1 = mid ，
                #  即 l 仍是二分的结果）
                r = mid - 1

        return l