編寫(xiě)一個(gè)高效的算法來(lái)搜索 m x n 矩陣 matrix 中的一個(gè)目標(biāo)值 target。該矩陣具有以下特性：

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

現(xiàn)有矩陣 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。

本題可以用暴力法，復(fù)雜度也沒(méi)有那么高，一個(gè)個(gè)元素進(jìn)行遍歷即可，O(MN)的復(fù)雜度，這樣的話(huà)就是沒(méi)有利用到這個(gè)二維數(shù)組的特性，我們來(lái)看一看這個(gè)數(shù)組有什么樣的特點(diǎn)。
從左到右是升序，從上到下是升序，因此我們?nèi)绻麖淖笙陆腔蛘哂疑辖情_(kāi)始遍歷，當(dāng)目標(biāo)值比目前遍歷的值大或者小都可以刪去一行或一列。
我們來(lái)舉個(gè)例子，從18開(kāi)始遍歷，如果目標(biāo)值是5，那么就是比18小，那么18的右邊是不可能考慮的，因此我們可以直接上移一行，同理，如果目標(biāo)值是20，那么就是比18大，那么18的上面是不用再考慮的，我們可以直接右移一列。
因此復(fù)雜度居然只要O(M+N)。

• 做這種題一定要冷靜分析數(shù)組的特征，抓住數(shù)組的特征來(lái)求解，有時(shí)候不一定一定要用什么算法，本題我一開(kāi)始就往二分查找算法想了很久，往往需要遍歷找某值的題目可以先想一想遍歷起點(diǎn)的選擇，可以大大簡(jiǎn)化復(fù)雜度。
  代碼如下:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        
        int i = row - 1, j = 0;
        while ( i >= 0 && j < matrix[0].length){
            if (matrix[i][j] > target) {
                i--;
            }
            else if (matrix[i][j] < target){
                j++;
            }
            else if (matrix[i][j] == target){
                return true;
            }
        }
        return false;
    }
}

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。