给定一个n x n的矩阵matrix,矩阵的每一行和每一列都按升序排列。下面代码返回矩阵中第k小的元素,则两处横线上应分别填写()。
def countLE(matrix, x):
n = len(matrix)
i, j = n - 1, 0
cnt = 0
while i >= 0 and j < n:
if matrix[i][j] <= x:
cnt += i + 1
j += 1
else:
i -= 1
return cnt
def kthSmallest(matrix, k):
n = len(matrix)
lo = matrix[0][0]
hi = matrix[n-1][n-1]
while lo < hi:
mid = lo + (hi - lo) // 2
if countLE(matrix, mid) >= k:
________
else:
________
return lo