一身转战三千里
一剑曾当百万师
这个题目还蛮有意思的。
按值二分而不是按索引二分。
首先设想一个场景，在如下的矩阵中：
[ 1, 5, 9]
[10, 11, 13]
[12, 13, 15]
如何快速找到矩阵中<= 14的数的个数呢？
找的方法可以参考剑指offer：二维数组中的查找。有两种找法，从左下角或者是右上角，比如从右上角开始，那样就往左下角移动，比如9 <= 14，那样就下移，比如15 > 14，就左移，就会把矩阵用阶梯状分割开来
[ 1 5 9|]
[10 11 13|]
——
[12 13 | 15]
———————
左上角是<= 14的部分，右下角是> 14的部分。这样就能找到矩阵中<= 14的数的个数。
通过对整个矩阵的值域进行二分，能够通过找到满足 矩阵中<= x 的个数是>= k，而值域[left, right]最终收敛成一个数。
这个数就是答案。
下面是代码：
class Solution {
private:
int not_greater(vector<vector<int>>& matrix, int n, int target) {
int i = 0, j = n - 1;
v = -1;
int cnt = 0;
while (i < n && j >= 0) {
if (target >= matrix[i][j]) {
v = max(matrix[i][j], v);
i++;
cnt += j + 1;
} else j--;
}
return cnt;
}
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
int leftv = matrix[0][0];
int rightv = matrix[n-1][n-1];
while (leftv < rightv) {
int midv = (leftv + rightv) / 2;
int cnt = not_greater(matrix, n, midv);
if (cnt >= k)
rightv = midv;
else if (cnt < k)
leftv = midv + 1;
}
return rightv;
}
};
