有序矩陣中第K小的元素
今天繼續(xù)是一道有關查找的題目，來自leetcode，難度為中等。
昨天我們分享了一道關于二分查找的題目``，今天我們再來看一道類似的題目，不過這里不在是數(shù)組，而是矩陣。
題目如下
給定一個 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查看更多題目
解題思路
思路一
在昨天分享的題目中，我們的第一個思路：先合并兩個數(shù)組（可以真正的開辟空間存儲合并后的數(shù)組，也可以只做歸并排序的合并邏輯，不需真的開辟存儲空間），再從合并后的數(shù)組中取第k個（或中位數(shù)）。
這道題目中我們可以采用類似的做法，即將矩陣的每一行看成是一個有序數(shù)組，這樣就將二個數(shù)組擴展到了n個數(shù)組。同樣采用先合并再取第k個數(shù)的邏輯。
同樣，根據昨天的經驗，這里我們先不寫代碼，先考慮能不能優(yōu)化空間復雜度，因為是矩陣合并成一個數(shù)組，所需空間和矩陣元素個數(shù)成正比，即O(n^2)。
在昨天的題目中，我們不需要真的存儲合并后的數(shù)組。同樣，這里也不需要，只需要存儲前k個數(shù)就夠了。那么，我們很自然的可以想到用優(yōu)先隊列。
因為使用了優(yōu)先隊列，所以這里的時間復雜度是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。怎么比較呢？
在有序數(shù)組中可以和數(shù)組的中間值array[n/2]進行比較，因為中間值左邊的值都比它小，右邊的值都比它大。那么在矩陣中可以和矩陣中間的值matrix[n/2][n/2]比較嗎？
仔細想一下的話發(fā)現(xiàn)是不行的，因為在有序矩陣中，雖然可以保證中間值左上方的值比它小，右下方的值比它大；但是左下和右上的值的大小無法判斷。
思考一下就可以發(fā)現(xiàn)我們可以和matrix[0][n]或者matrix[n][0]比較，用該值和mid比較，雖然不能像二分查找每次都去掉一半的值，這里每次都可以去掉一行或者一列。
有了比較的方法，剩下的問題是如何計算是第k個？
第k小的數(shù)字意味著小于等于它的元素一共有k個。思路如下，這里我們選擇和val=matrix[n][0]比較：如果val小于mid，這該行都小于mid，則比該值小的個數(shù)count加上n；如果val的值比mid值大，則繼續(xù)比較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;
}
從上面代碼可以看出，二分查找的次數(shù)為log(max - min)，這里max，min表示矩陣的最大，最小元素的值。每次查找訪問數(shù)組（進行比較）2*n次，其時間復雜度為2nlog(max - min)。空間復雜度為O(1)
總結
這道題還是重點考察對于二分查找的理解和使用，這里從數(shù)組擴展到了矩陣，其思路是一樣的，用二分查找的方法將時間復雜度降為 log 級別。
