題目描述：
給定一個(gè)?n x n?矩陣，其中每行和每列元素均按升序排序，找到矩陣中第 k 小的元素。請(qǐng)注意，它是排序后的第 k 小元素，而不是第 k 個(gè)不同的元素。
難度：中等
示例：
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
看到這個(gè)題，我首先就想到了優(yōu)先隊(duì)列。在查找第k個(gè)大小的元素時(shí)，小頂堆是一個(gè)非常不錯(cuò)的選擇。Java自帶的小頂堆為PriorityQueue，也就是優(yōu)先隊(duì)列。先將所有數(shù)組中所有元素放入棧中，然后從小頂堆中彈出k個(gè)元素即可，第k個(gè)元素即為答案。
public static int kthSmallest(int[][] matrix, int k) {
????????//維護(hù)一個(gè)小頂堆，然后彈出K個(gè)元素
? ????? 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();
}
優(yōu)先隊(duì)列的插入和刪除操作時(shí)間復(fù)雜度為logn，所以總的時(shí)間復(fù)雜度為O（n*n*logn）
然而這種解法沒有利用到題目所給到的矩陣的特性。所以雖然寫起來簡(jiǎn)單，但時(shí)間復(fù)雜度實(shí)在是難以讓人滿意。
所以我們要充分利用這個(gè)矩陣的特性。我們可以從矩陣的最大值max與最小值min之間取一個(gè)數(shù)mid。然后從矩陣左下角出發(fā)，當(dāng)matrix[i][j]小于等于mid則說明第j列i行以上的元素都小于等于mid.統(tǒng)計(jì)下這些元素的個(gè)數(shù)num。然后將j+1，即右移一步。若matrix[i][j]大于mid，則第i行第j列右邊的元素也都大于mid，這些大于mid的元素就不需要記錄了，這個(gè)時(shí)候我們需要向上走一步使得i-1，這樣當(dāng)前的matrix[i][j]更小。直到統(tǒng)計(jì)完所有小于等于mid的數(shù)。
當(dāng)然，我們其實(shí)也可以從矩陣的右上角出發(fā)，matrix[i][j]小于等于mid則說明第i行j列左邊的的元素都小于等于mid.之后的操作雖然不一樣，但是核心思想是一樣的，記錄下小于等于mid的數(shù)即可
若是num>=k則說明此時(shí)mid的大小不小于答案answer。即此時(shí)mid>=answer.
若是num<k則說明此時(shí)mid的大小大于答案answer，即mid<answer.
對(duì)于mid>=answer的情況我們需要將min減小，對(duì)于mid<answer的情況則需要使得mid增大
public static int kthSmallest2(int[][] matrix, int k) {
? ? ????????//每次選取一個(gè)處于max與min之間的數(shù)mid，然后從左下角出發(fā)，計(jì)算比它小的數(shù)字? ????????????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，當(dāng)mid剛好等于ans時(shí)，這樣的操作會(huì)使得正確的ans被跳過，導(dǎo)致計(jì)算出的結(jié)果偏小。
? ? ? ????????????? }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;
}
