为了可快速解决问题用二分法，这一部分没得可说，用套路把二分法结构搭起来，值得一提的是如何快速算出int helper(vector<vector<int>>& matrix, int value) :算出<=value的个数
image.png
- code C++:
//my 从右上开始 best
int helper(vector<vector<int>>& matrix, int value) {
int i = 0, j = matrix[0].size() - 1;
int ans = 0;
while (j >= 0 && i < matrix.size()) {
if (matrix[i][j] <= value) {
ans += j + 1;
i++;
}
else
j--;
}
return ans;
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
int left = matrix[0][0], right = matrix.back().back();
while (left < right) {
int mid = left + (right - left) / 2;
int cnt = helper(matrix, mid);
if (cnt < k) {
left = mid + 1;
}
else
right = mid;
}
return right;
}
