有序矩阵中第K小的元素
今天继续是一道有关查找的题目，来自leetcode，难度为中等。
昨天我们分享了一道关于二分查找的题目``，今天我们再来看一道类似的题目，不过这里不在是数组，而是矩阵。
题目如下
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。示例:
matrix =
[
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。提示：
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
解题思路及代码见阅读原文
回复0000查看更多题目
解题思路
思路一
在昨天分享的题目中，我们的第一个思路：先合并两个数组（可以真正的开辟空间存储合并后的数组，也可以只做归并排序的合并逻辑，不需真的开辟存储空间），再从合并后的数组中取第k个（或中位数）。
这道题目中我们可以采用类似的做法，即将矩阵的每一行看成是一个有序数组，这样就将二个数组扩展到了n个数组。同样采用先合并再取第k个数的逻辑。
同样，根据昨天的经验，这里我们先不写代码，先考虑能不能优化空间复杂度，因为是矩阵合并成一个数组，所需空间和矩阵元素个数成正比，即O(n^2)。
在昨天的题目中，我们不需要真的存储合并后的数组。同样，这里也不需要，只需要存储前k个数就够了。那么，我们很自然的可以想到用优先队列。
因为使用了优先队列，所以这里的时间复杂度是O(n^2log(k))，空间复杂度为O(k)。
代码如下
Java版
public int kthSmallest(int[][] matrix, int k) {
PriorityQueue<Integer> MaxPQ = new PriorityQueue<>(Collections.reverseOrder());
for (int[] row : matrix) {
for (int num : row) {
if (MaxPQ.size() == k && num > MaxPQ.peek())
break;
MaxPQ.add(num);
if (MaxPQ.size() > k)
MaxPQ.remove();
}
}
return MaxPQ.remove();
}
思路二
和昨天的题目类似，我们没有充分理由矩阵是有序的这个条件，利用这个条件可以进一步的降低时间和空间复杂度，同样这里才有二分查找的思想解题，思路如下。
因为是有序矩阵，所以最小值是l = matrix[0][0]，最大值是r = matrix[n][n]，那么其中间值是mid = (l + r) / 2。怎么比较呢？
在有序数组中可以和数组的中间值array[n/2]进行比较，因为中间值左边的值都比它小，右边的值都比它大。那么在矩阵中可以和矩阵中间的值matrix[n/2][n/2]比较吗？
仔细想一下的话发现是不行的，因为在有序矩阵中，虽然可以保证中间值左上方的值比它小，右下方的值比它大；但是左下和右上的值的大小无法判断。
思考一下就可以发现我们可以和matrix[0][n]或者matrix[n][0]比较，用该值和mid比较，虽然不能像二分查找每次都去掉一半的值，这里每次都可以去掉一行或者一列。
有了比较的方法，剩下的问题是如何计算是第k个？
第k小的数字意味着小于等于它的元素一共有k个。思路如下，这里我们选择和val=matrix[n][0]比较：如果val小于mid，这该行都小于mid，则比该值小的个数count加上n；如果val的值比mid值大，则继续比较mid和matrix[n-1][0]的大小，以此类推，直到遍历完整个矩阵。思路有了，代码如下：
代码如下
public int kthSmallest2(int[][] matrix, int k) {
int n = matrix.length - 1;
int left = matrix[0][0], right = matrix[n][n];
while(left < right){
int mid = left + (right - left) / 2;
int count = countNotMoreThanMid(matrix, mid, n);
if(count < k)
left = mid + 1;
else
right = mid;
}
return left;
}
private int countNotMoreThanMid(int[][] matrix, int mid, int n){
int count = 0;
int x = 0, y = n;
while(x <= n && y >= 0){
if(matrix[y][x] <= mid){
count += y + 1;
x++;
}else{
y--;
}
}
return count;
}
从上面代码可以看出，二分查找的次数为log(max - min)，这里max，min表示矩阵的最大，最小元素的值。每次查找访问数组（进行比较）2*n次，其时间复杂度为2nlog(max - min)。空间复杂度为O(1)
总结
这道题还是重点考察对于二分查找的理解和使用，这里从数组扩展到了矩阵，其思路是一样的，用二分查找的方法将时间复杂度降为 log 级别。
