【LeetCode】378. 有序矩阵中第k小的元素

题目

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

题目

方法一

合并成一个一维数组之后排序，取出第k个。

方法二

二分查找。

由于矩阵是有排序关系的，任意取一个数num，该数在矩阵最小值和最大值之间，那么该数定可以把矩阵分成左右两半部分。左半部分是小于num的数，进一步可以把小于num的数的数量统计出来。右半部分同理。

可以二分去搜索这个数。

代码

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        def check(mid):
            i, j = n - 1, 0
            num = 0
            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
            print(mid, left, right)
        return left