Problem
LeetCode 378. Kth Smallest Element in a Sorted Matrix
1. 题目简述
给出一个m * n大小的矩阵，找出其第k大的数：
- 每一行从左到右都是递增的整形数
- 每一列从上至下都是递增的整形数
例如：
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.
2. 算法思路
相关问题：
这道题和LeetCode 240. Search a 2D Matrix II特别像，基本上是一个模子里出来的，只不过这个更麻烦一些，它并不是去找某个数那样明确的目标，而是一个比较间接的值，需要做一些小改变。
按照我们正常的思路，start和end分别是左上角和右下角，但是我们的mid并不一定在matrix中存在，我们也不能用mid + 1或者mid - 1来更新start和end。因此，我们要做的有两件事：
（1）记录全局数组中小于等于mid值的个数。
（2）需要更新的值，也就是比mid小的最大值和比mid大的最小值。
二分搜索
我们还需要注意一点，数组中可能存在重复的值，就像例子里那样，13是我们的target，但是13有两个，也就是说我们找第7小的数和第8小的数都是13，如果我们找第7个，那么当我们遍历到13的时候，我们得到的个数永远都是8，8 > 7，然后我们应该让end减小，但是小于等于13的最大的数还是13，因为我们这里有两个13，就无限循环了，start是13，end也是13.
所以，我们要注意的点就是二分搜索的循环条件，这里如果l == r，则说明当前值即为所求，不要再继续循环了。这一点一定要注意！
class Solution {
public int kthSmallest(int[][] matrix, int k) {
// 由于横竖都有序，所以用二分搜索继续查找也是有一定规律的，我们可以从右上或者左下进行查找，可以记一个小tips。smallLargeNumber用于记录小于middle的最大值和大于middle的最小值。
int n = matrix.length, l = matrix[0][0], r = matrix[n - 1][n - 1];
// 注意这里的循环结束条件，不是l <=r
while (l < r) {
int m = l + (r - l) / 2;
int[] smallLargeNumber = new int[2];
int count = countLessEqual(matrix, m, smallLargeNumber);
if (count < k) {
l = smallLargeNumber[1];
} else if (count > k) {
r = smallLargeNumber[0];
} else {
return smallLargeNumber[0];
}
}
return l;
}
private int countLessEqual(int[][] matrix, int middle, int[] smallLargeNumber) {
int n = matrix.length;
int count = 0, row = 0, col = n - 1;
smallLargeNumber[0] = Integer.MIN_VALUE;
smallLargeNumber[1] = Integer.MAX_VALUE;
while (row < n && col >= 0) {
if (matrix[row][col] > middle) {
smallLargeNumber[1] = Math.min(smallLargeNumber[1], matrix[row][col]);
col--;
} else {
smallLargeNumber[0] = Math.max(smallLargeNumber[0], matrix[row][col]);
count += col + 1;
row++;
}
}
return count;
}
}