<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>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0240. 搜索二維矩陣 II ## 題目地址(240. 搜索二維矩陣 II) <https://leetcode-cn.com/problems/search-a-2d-matrix-ii/> ## 題目描述 ``` <pre class="calibre18">``` 編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標值 target。該矩陣具有以下特性: 每行的元素從左到右升序排列。 每列的元素從上到下升序排列。 示例: 現有矩陣 matrix 如下: [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 給定 target = 5,返回 true。 給定 target = 20,返回 false。 ``` ``` ## 前置知識 - 數組 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 符合直覺的做法是兩層循環遍歷,時間復雜度是O(m \* n), 有沒有時間復雜度更好的做法呢? 答案是有,那就是充分運用矩陣的特性(橫向縱向都遞增), 我們可以從角落(左下或者右上)開始遍歷,這樣時間復雜度是O(m + n). ![](https://img.kancloud.cn/e4/f4/e4f4d0371b92c9b1f7b8b21058ee3a32_569x400.jpg) 其中藍色代表我們選擇的起點元素, 紅色代表目標元素。 ## 關鍵點解析 - 從角落開始遍歷,利用遞增的特性簡化時間復雜 ## 代碼 代碼支持:JavaScript, Python3 JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=240 lang=javascript * * [240] Search a 2D Matrix II * * https://leetcode.com/problems/search-a-2d-matrix-ii/description/ * * */</span> <span class="hljs-title">/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */</span> <span class="hljs-keyword">var</span> searchMatrix = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">matrix, target</span>) </span>{ <span class="hljs-keyword">if</span> (!matrix || matrix.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">let</span> colIndex = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> rowIndex = matrix.length - <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span>(rowIndex > <span class="hljs-params">0</span> && target < matrix[rowIndex][colIndex]) { rowIndex --; } <span class="hljs-keyword">while</span>(colIndex < matrix[<span class="hljs-params">0</span>].length) { <span class="hljs-keyword">if</span> (target === matrix[rowIndex][colIndex]) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">if</span> (target > matrix[rowIndex][colIndex]) { colIndex ++; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (rowIndex > <span class="hljs-params">0</span>){ rowIndex --; } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } } <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">searchMatrix</span><span class="hljs-params">(self, matrix, target)</span>:</span> m = len(matrix) <span class="hljs-keyword">if</span> m == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> n = len(matrix[<span class="hljs-params">0</span>]) i = m - <span class="hljs-params">1</span> j = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> i >= <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> j < n: <span class="hljs-keyword">if</span> matrix[i][j] == target: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">if</span> matrix[i][j] > target: i -= <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: j += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> ``` ``` **復雜度分析** - 時間復雜度:O(M+N)O(M + N)O(M+N) - 空間復雜度:O(1)O(1)O(1) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 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>

                              哎呀哎呀视频在线观看