题干
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
示例：
matrix
= [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k
= 8,
返回
13。
提示： 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。
二分法
给定一个矩阵里的数matrix[i][j],比它小的一定在左上方。
于是从矩阵左下角开始二分， 它的上边都比它小。 统计此位置比mid小的个数在进行指针变换即可
Java
package daily
;
public class KthSmallest {
public int kthSmallest(int[][] matrix
, int k
) {
int n
= matrix
.length
;
int left
= matrix
[0][0];
int right
= matrix
[n
- 1][n
- 1];
while (left
< right
) {
int mid
= left
+ ((right
- left
) >> 1);
if (check(matrix
, mid
, k
, n
)) {
right
= mid
;
} else {
left
= mid
+ 1;
}
}
return left
;
}
public boolean check(int[][] matrix
, int mid
, int k
, int n
) {
int i
=n
-1;
int j
=0;
int sum
=0;
while(i
>=0&&j
<n
){
if(matrix
[i
][j
]<=mid
){
sum
+=i
+1;
j
++;
}
else {
i
--;
}
}
return sum
>=k
;
}
}
我的leetcode代码都已经上传到我的githttps://github.com/ragezor/leetcode
