# 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).  其中藍色代表我們選擇的起點元素， 紅色代表目標元素。 ## 關鍵點解析 - 從角落開始遍歷，利用遞增的特性簡化時間復雜 ## 代碼 代碼支持：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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。