<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 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 小則說明中間值太小了,則向后移動,否則向前移動。 這個題目的二分確實很難想,我們來一步一步解釋。 最普通的二分法是有序數組中查找指定值(或者說滿足某個條件的值)。由于是有序的,我們可以根據索引關系來確定大小關系, 因此這種思路比較直接,但是對于這道題目索引大小和數字大小沒有直接的關系,因此這種二分思想就行不通了。 ![](https://img.kancloud.cn/64/dd/64dd116c431421290028d0bf49f7ba7d_587x138.jpg) (普通的基于索引判斷的二分法) - 我們能夠找到矩陣中最大的元素(右下角)和最小的元素(左上角)。我們可以求出值的中間,而不是上面那種普通二分法的索引的中間。 ![](https://img.kancloud.cn/a0/1d/a01dc470af7c45558f3be32b11d21f76_449x195.jpg) - 找到中間值之后,我們可以拿這個值去計算有多少元素是小于等于它的。 具體方式就是比較行的最后一列,如果中間值比最后一列大,說明中間元素肯定大于這一行的所有元素。 否則我們從后往前遍歷直到不大于。 ![](https://img.kancloud.cn/44/04/4404c2f468d0e8a73ac36199f83414a7_430x226.jpg) - 上一步我們會計算一個count,我們拿這個count和k進行比較 - 如果count小于k,說明我們選擇的中間值太小了,肯定不符合條件,我們需要調整左區間為mid + 1 - 如果count大于k,說明我們選擇的中間值正好或者太大了。我們調整右區間 mid > 由于count大于k 也可能我們選擇的值是正好的, 因此這里不能調整為mid - 1, 否則可能會得不到結果 - 最后直接返回start, end, 或者 mid都可以,因此三者最終會收斂到矩陣中的一個元素,這個元素也正是我們要找的元素。 整個計算過程是這樣的: ![](https://img.kancloud.cn/46/71/46717ff6080a63c834e1c34657be7d35_698x566.jpg) 這里有一個大家普遍都比較疑惑的點,也是我當初非常疑惑,困擾我很久的點, 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看