給你一個 n x n 矩陣 matrix ，其中每行和每列元素均按升序排序，找到矩陣中第 k 小的元素。
請注意，它是 排序后 的第 k 小元素，而不是第 k 個 不同 的元素。
你必須找到一個內存復雜度優于 O(n2) 的解決方案。
示例 1：
輸入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
輸出：13
解釋：矩陣中的元素為 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
示例 2：
輸入：matrix = [[-5]], k = 1
輸出：-5
提示：
n == matrix.length
n == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109
題目數據 保證 matrix 中的所有行和列都按 非遞減順序 排列
1 <= k <= n2
題解
有序 ＋ 確定范圍 可以使用二分查找
- 左上角matrix[0][0]是下限，右下角matrix[n-1][n-1]是上限，就有了一個值，第 k 小的元素在這個值域中
我們對值域進行二分查找(mid=(matrix[0][0]+matrix[n-1][n-1])/2)，使得mid逼近值域中的目標值(第 k 小的元素) - 求出矩陣里小于等于mid的有幾個，num個
- num 和 k 比較
如果比 k 小，說明中間值小了，調整值域范圍(left=mid+1)
否則，說明中間值大了，調整值域范圍(right=mid)，一步步鎖定目標值
注：
1. 為什么對值二分而不是對索引二分
二分查找可以根據索引二分，也可以根據數值二分，有序數組中，索引的大小可以反映值的大小，對索引二分就行
但這里不是有序的一維數組，索引不能體現值誰大誰小，無法通過二分索引逼近目標值
2. 為什么最后left是第k小的數||二分法如何保證最后的left or right 是數組中的元素？
因為每次值域收縮都保證了第 k 小的數在 left ~ right 之間，當 left==right 時，第 k 小的數即被找出，等于left
class Solution {public int kthSmallest(int[][] matrix, int k) {int n = matrix.length;//left和right是矩陣值不是矩陣下標int left = matrix[0][0];int right = matrix[n - 1][n - 1];//一步步收縮值域范圍直至left==right//因為每次值域收縮都保證了第 k 小的數在 left ~ right 之間，當 left==right 時，第 k 小的數即被找出，等于leftwhile (left < right) {//避免溢出int mid = left + (right - left)/2;//滿足 num >= k，范圍太大，移動right至mid， 范圍收縮//注意num=k時說明小于等于mid數的數量等于k，但不代表mid就是結果，因為此時mid不一定在matrix中if (check(matrix, mid, k, n)) {right = mid;} else {//滿足 num < k，范圍太小，移動left至mid+1， 范圍收縮left = mid + 1;}}//跳出循環時left=right,返回值left是什么？？？return left;}//從矩陣左下角開始按列遍歷每一列，計算每一列中比mid小的元素個數并累加獲得num，將num與k比較//返回值boolean：矩陣中小于mid的數>=k//為什么不直接返回num=k時的mid值？因為mid是通過值域二分法計算出的值，不是實際的矩陣值public boolean check(int[][] matrix, int mid, int k, int n) {int i = n - 1;int j = 0;int num = 0;while (i >= 0 && j < n) {if (matrix[i][j] <= mid) {//當前元素小于mid，則本列此元素及上方元素均小于mid，num+=i+1（行號是i,行的數目是i+1）num += i + 1;//列向右移動，計算下一列小于mid的元素的個數j++;} else {//當前元素大于mid，則向上移動，直到找到比mid小的值，或者出矩陣i--;}}return num>=k;}}
)
