378. 有序矩阵中第K小的元素
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
思路
考虑到是在有序矩阵中寻找第K小元素，肯定会用到矩阵的特性，由于矩阵左上角是最小元素min，右下角为最大元素max，相当于框定了一个范围，假定min<mid<max，那么小于或者等于mid的元素肯定在左上方，那么我们依次从矩阵的左下角开始统计有多少个num元素小于或等于mid，当num>=k时，证明mid应该减少，否则mid应该增大，符合二分法的思路。
代码
class Solution {
public:
int check(vector
<vector
<int>>& matrix
, int m
, int n
, int mid
, int k
) {
int i
= m
- 1;
int j
= 0;
int num
= 0;
while(i
>= 0 && j
< n
) {
if(matrix
[i
][j
] <= mid
) {
num
+= i
+ 1;
j
++;
}
else {
i
--;
}
}
return num
>= k
;
}
int kthSmallest(vector
<vector
<int>>& matrix
, int k
) {
int m
= matrix
.size();
int n
= matrix
[0].size();
int left
= matrix
[0][0];
int right
= matrix
[m
- 1][n
- 1];
while(left
< right
) {
int mid
= left
+ (right
- left
) / 2;
if(check(matrix
, m
, n
, mid
, k
)) {
right
= mid
;
}
else {
left
= mid
+ 1;
}
}
return left
;
}
};
