给定 个 n x n 的矩阵 matrix ，矩阵的每 和每 列都按升序排列。函数 countLE 返回矩阵中第 一 一 行 一 k 的元素，则两处横线上应分别填写（ ）。 小
// 统计矩阵中 <= x 的元素个数：从左下角开始
int countLE(const vector<vector<int>>& matrix, int x) {
int n = (int)matrix.size();
int i = n - 1, j = 0, cnt = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] <= x) {
cnt += i + 1;
++j;
}
else {
--i;
}
}
return cnt;
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = (int)matrix.size();
int lo = matrix[0][0];
int hi = matrix[n - 1][n - 1];
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (countLE(matrix, mid) >= k) {
________________ // 在此处填入代码
} else {
________________ // 在此处填入代码
}
}
return lo;
}
- A. 1 hi = mid - 1; 2 lo = mid + 1;
- B. 1 hi = mid; 2 lo = mid;
- C. 1 hi = mid; 2 lo = mid + 1;
- D. 1 hi = mid + 1; 2 lo = mid;
正确答案：C