第84天：100天DSA编码挑战

Source: Dev.to

问题

GeeksforGeeks – 矩阵中的第 k 小元素

难度： 中等 | 准确率： 61.42%

给定一个大小为 n × n 的矩阵 mat[][]，其中每行和每列都按非递减顺序排序，找出矩阵中的第 k 小元素。

解法

class Solution:
    def kthSmallest(self, mat, k):
        n = len(mat)
        low, high = mat[0][0], mat[-1][-1]

        while low < high:
            mid = (low + high) // 2
            count = 0

            # Count elements ≤ mid in each row using binary search
            for row in mat:
                l, r = 0, n
                while l < r:
                    m = (l + r) // 2
                    if row[m] <= mid:
                        l = m + 1
                    else:
                        r = m
                count += l

            if count < k:
                low = mid + 1
            else:
                high = mid

        return low