日拱演算法：搜尋二維矩陣 II

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第28天，點選檢視活動詳情

---

xixixi，更文無力，轉攻演算法簡單題。中難題畏畏縮縮，簡單題我重拳出擊~~

題：

• 題目來源：LeetBook /演算法面試題彙總

編寫一個高效的演算法來搜尋 m x n 矩陣 matrix 中的一個目標值 target 。該矩陣具有以下特性：

每行的元素從左到右升序排列。 每列的元素從上到下升序排列。

示例 1：

輸入：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

輸入：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 = 20 輸出：false

解：

此題要利用到【每行的元素從左到右升序排列。 每列的元素從上到下升序排列】這個關鍵的題幹資訊。

咱就是說，只要是查詢目標值，有了排序，都會方便許多。

思路：從矩陣的右上角（或左下角）的值開始比較；

比如：從矩陣右上角的值開始找，那就是第一行的最後一個數字；

1. 如果目標值剛好等於右上角的值，則返回輸出；
2. 如果目標值小於右上角值，則目標值肯定是在同一行的左邊去找；
3. 如果目標值大於右上角的值，則到下一行去找；

```js var searchMatrix = function(matrix, target) { let col = matrix[0].length - 1;//列 let row = 0;//行

    while (col >= 0 && row <= matrix.length - 1) {
        if (target == matrix[row][col]) {
            //如果找到就直接返回
            return true;
        } else if (target < matrix[row][col]) {
            //目標值小於右上角值，下一步往左找
            col--;
        } else if (target > matrix[row][col]) {
            //目標值大於右上角值，下一步往下找
            row++;
        }
    }
    return false;

}; ``` 那麼，相應的，從左下角，找的思路就是反過來的，不做贅述：

js var searchMatrix = function(matrix, target) { let col = 0, row = matrix.length - 1; while(row >= 0 && col < matrix[0].length){ if(target > matrix[row][col]){ col++; }else if(target < matrix[row][col]){ row--; }else{ return true; } } return false; };

OK，以上便是本篇分享。點贊關注評論，為好文助力👍

我是掘金安東尼 🤠 100 萬閱讀量人氣前端技術博主 💥 INFP 寫作人格堅持 1000 日更文 ✍ 關注我，陪你一起度過漫長程式設計歲月 🌏