给定一个 ( n \times 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
hi = mid - 1; lo = mid + 1;
hi = mid; lo = mid;
hi = mid; lo = mid + 1;
hi = mid + 1; lo = mid;