题目描述：
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
难度：中等
示例：
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
看到这个题，我首先就想到了优先队列。在查找第k个大小的元素时，小顶堆是一个非常不错的选择。Java自带的小顶堆为PriorityQueue，也就是优先队列。先将所有数组中所有元素放入栈中，然后从小顶堆中弹出k个元素即可，第k个元素即为答案。
public static int kthSmallest(int[][] matrix, int k) {
//维护一个小顶堆，然后弹出K个元素
Queue queue =new PriorityQueue<>();
for (int i =0; i < matrix.length; i++)
for (int j =0; j < matrix.length; j++) {
queue.add(matrix[i][j]);
}
while (k >1) {
queue.poll();
k--;
}
return queue.poll();
}
优先队列的插入和删除操作时间复杂度为logn，所以总的时间复杂度为O（n*n*logn）
然而这种解法没有利用到题目所给到的矩阵的特性。所以虽然写起来简单，但时间复杂度实在是难以让人满意。
所以我们要充分利用这个矩阵的特性。我们可以从矩阵的最大值max与最小值min之间取一个数mid。然后从矩阵左下角出发，当matrix[i][j]小于等于mid则说明第j列i行以上的元素都小于等于mid.统计下这些元素的个数num。然后将j+1，即右移一步。若matrix[i][j]大于mid，则第i行第j列右边的元素也都大于mid，这些大于mid的元素就不需要记录了，这个时候我们需要向上走一步使得i-1，这样当前的matrix[i][j]更小。直到统计完所有小于等于mid的数。
当然，我们其实也可以从矩阵的右上角出发，matrix[i][j]小于等于mid则说明第i行j列左边的的元素都小于等于mid.之后的操作虽然不一样，但是核心思想是一样的，记录下小于等于mid的数即可
若是num>=k则说明此时mid的大小不小于答案answer。即此时mid>=answer.
若是num<k则说明此时mid的大小大于答案answer，即mid<answer.
对于mid>=answer的情况我们需要将min减小，对于mid<answer的情况则需要使得mid增大
public static int kthSmallest2(int[][] matrix, int k) {
//每次选取一个处于max与min之间的数mid，然后从左下角出发，计算比它小的数字 num。
//若num>=k则减小mid的值，反之则缩小
int min = matrix[0][0];
int max = matrix[matrix.length -1][matrix.length -1];
while (min < max) {
int mid = ((max - min) >>1) + min;
if (countSmaller(matrix, mid) >= k) {
max = mid;//不能写mid-1，当mid刚好等于ans时，这样的操作会使得正确的ans被跳过，导致计算出的结果偏小。
}else {
min = mid +1;
}
}
return min;
}
private static int countSmaller(int[][] matrix, int mid) {
int num =0;
int i = matrix.length -1;
int j =0;
while (i >=0 && j < matrix.length) {
if (matrix[i][j] <=mid) {//若matrix[i][j]小于等于mid则说明第j列i行以上的元素都小于等于mid
j++;
num += i +1;
}else {//若matrix[i][j]大于mid，则第i行第j列右边的元素也都大于mid，所以不需要累加num
i--;
}
}
return num;
}
