# 0378. 有序矩陣中第K小的元素 ## 題目地址(378. 有序矩陣中第K小的元素) <https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個 n x n 矩陣，其中每行和每列元素均按升序排序，找到矩陣中第 k 小的元素。 請注意，它是排序后的第 k 小元素，而不是第 k 個不同的元素。 示例： matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, 返回 13。 提示： 你可以假設 k 的值永遠是有效的，1 ≤ k ≤ n2 。 ``` ``` ## 前置知識 - 二分查找 - 堆 ## 公司 - 阿里 - 騰訊 - 字節 ## 思路 顯然用大頂堆可以解決，時間復雜度 Klogn n 為總的數字個數, 但是這種做法沒有利用題目中 sorted matrix 的特點，因此不是一種好的做法. 一個巧妙的方法是二分法，我們分別從第一個和最后一個向中間進行掃描，并且計算出中間的數值與數組中的進行比較， 可以通過計算中間值在這個數組中排多少位，然后得到比中間值小的或者大的數字有多少個，然后與 k 進行比較，如果比 k 小則說明中間值太小了，則向后移動，否則向前移動。 這個題目的二分確實很難想，我們來一步一步解釋。 最普通的二分法是有序數組中查找指定值（或者說滿足某個條件的值）。由于是有序的，我們可以根據索引關系來確定大小關系， 因此這種思路比較直接，但是對于這道題目索引大小和數字大小沒有直接的關系，因此這種二分思想就行不通了。  (普通的基于索引判斷的二分法) - 我們能夠找到矩陣中最大的元素（右下角）和最小的元素（左上角）。我們可以求出值的中間，而不是上面那種普通二分法的索引的中間。  - 找到中間值之后，我們可以拿這個值去計算有多少元素是小于等于它的。 具體方式就是比較行的最后一列，如果中間值比最后一列大，說明中間元素肯定大于這一行的所有元素。 否則我們從后往前遍歷直到不大于。  - 上一步我們會計算一個count，我們拿這個count和k進行比較 - 如果count小于k，說明我們選擇的中間值太小了，肯定不符合條件，我們需要調整左區間為mid + 1 - 如果count大于k，說明我們選擇的中間值正好或者太大了。我們調整右區間 mid > 由于count大于k 也可能我們選擇的值是正好的， 因此這里不能調整為mid - 1， 否則可能會得不到結果 - 最后直接返回start, end, 或者 mid都可以，因此三者最終會收斂到矩陣中的一個元素，這個元素也正是我們要找的元素。 整個計算過程是這樣的：  這里有一個大家普遍都比較疑惑的點，也是我當初非常疑惑，困擾我很久的點， leetcode評論區也有很多人來問，就是“能夠確保最終我們找到的元素一定在矩陣中么？” 答案是可以, `相等的時候一定在matrix里面。 因為原問題一定有解，找下界使得start不斷的逼近于真實的元素`. 我是看了評論區一個大神的評論才明白的，以下是[@GabrielaSong](https://leetcode.com/gabrielasong/)的評論原文： ``` <pre class="calibre18">``` The lo we returned is guaranteed to be an element in the matrix is because: Let us assume element m is the kth smallest number in the matrix, and x is the number of element m in the matrix. When we are about to reach convergence, if mid=m-1, its count value (the number of elements which are <= mid) would be k-x, so we would set lo as (m-1)+1=m, in this case the hi will finally reach lo; and if mid=m+1, its count value would be k+x-1, so we would set hi as m+1, in this case the lo will finally reach m. To sum up, because the number lo found by binary search find is exactly the element which has k number of elements in the matrix that are <= lo, The equal sign guarantees there exists and only exists one number in range satisfying this condition. So lo must be the only element satisfying this element in the matrix. ``` ``` 更多解釋,可以參考[leetcode discuss](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85173/Share-my-thoughts-and-Clean-Java-Code) > 如果是普通的二分查找，我們是基于索引去找，因此不會有這個問題。 ## 關鍵點解析 - 二分查找 - 有序矩陣的套路（文章末尾還有一道有序矩陣的題目） - 堆（優先級隊列） ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=378 lang=javascript * * [378] Kth Smallest Element in a Sorted Matrix */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">notGreaterCount</span>(<span class="hljs-params">matrix, target</span>) </span>{ <span class="hljs-title">// 等價于在matrix 中搜索mid，搜索的過程中利用有序的性質記錄比mid小的元素個數</span> <span class="hljs-title">// 我們選擇左下角，作為開始元素</span> <span class="hljs-keyword">let</span> curRow = <span class="hljs-params">0</span>; <span class="hljs-title">// 多少列</span> <span class="hljs-keyword">const</span> COL_COUNT = matrix[<span class="hljs-params">0</span>].length; <span class="hljs-title">// 最后一列的索引</span> <span class="hljs-keyword">const</span> LAST_COL = COL_COUNT - <span class="hljs-params">1</span>; <span class="hljs-keyword">let</span> res = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (curRow < matrix.length) { <span class="hljs-title">// 比較最后一列的數據和target的大小</span> <span class="hljs-keyword">if</span> (matrix[curRow][LAST_COL] < target) { res += COL_COUNT; } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">let</span> i = COL_COUNT - <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span> (i < COL_COUNT && matrix[curRow][i] > target) { i--; } <span class="hljs-title">// 注意這里要加1</span> res += i + <span class="hljs-params">1</span>; } curRow++; } <span class="hljs-keyword">return</span> res; } <span class="hljs-title">/** * @param {number[][]} matrix * @param {number} k * @return {number} */</span> <span class="hljs-keyword">var</span> kthSmallest = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">matrix, k</span>) </span>{ <span class="hljs-keyword">if</span> (matrix.length < <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">null</span>; <span class="hljs-keyword">let</span> start = matrix[<span class="hljs-params">0</span>][<span class="hljs-params">0</span>]; <span class="hljs-keyword">let</span> end = matrix[matrix.length - <span class="hljs-params">1</span>][matrix[<span class="hljs-params">0</span>].length - <span class="hljs-params">1</span>]; <span class="hljs-keyword">while</span> (start < end) { <span class="hljs-keyword">const</span> mid = start + ((end - start) >> <span class="hljs-params">1</span>); <span class="hljs-keyword">const</span> count = notGreaterCount(matrix, mid); <span class="hljs-keyword">if</span> (count < k) start = mid + <span class="hljs-params">1</span>; <span class="hljs-keyword">else</span> end = mid; } <span class="hljs-title">// 返回start,mid, end 都一樣</span> <span class="hljs-keyword">return</span> start; }; ``` ``` **復雜度分析** - 時間復雜度：二分查找進行次數為 O(log(r?l))O(log(r-l))O(log(r?l))，每次操作時間復雜度為 O(n)，因此總的時間復雜度為 O(nlog(r?l))O(nlog(r-l))O(nlog(r?l))。 - 空間復雜度：O(1)O(1)O(1)。 ## 相關題目 - [240.search-a-2-d-matrix-ii](240.search-a-2-d-matrix-ii.html) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。