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

語言: CN / TW / HK

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


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

image.png

題:

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

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

示例 1:

image.png

輸入: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 searchgrid.jpg

輸入: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; };

image.png

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

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