題目描述
在一個(gè) n * m 的二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
示例:
現(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。
限制：
0 <= n <= 1000
0 <= m <= 1000
解題思路
最容易想到的就是暴力遍歷矩陣，但是由于題目給出的矩陣具有一定規(guī)律性，所以在看了Leetcode上精選的題解后，還是挺巧妙的。首先從矩陣最左下角的元素a開始進(jìn)行判斷，當(dāng)taget<a時(shí)，則忽略改行，往上遍歷；當(dāng)target>a時(shí)，則忽略該列，往右遍歷。直到遍歷到與target值相等，輸出True。否則將整個(gè)矩陣都遍歷完成之后還是不能找到與target值相等的數(shù)，則輸出False.

程序代碼

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        #len(matrix)是矩陣行數(shù)，len(matrix[0])是矩陣列數(shù)
        i, j = len(matrix) - 1, 0 
        while i >= 0 and j < len(matrix[0]):
            if matrix[i][j] > target:
                i -= 1
            elif matrix[i][j] < target:
                j += 1
            else:
                return True
        
        return False

復(fù)雜度分析

• 時(shí)間復(fù)雜度：其中和分別是矩陣行數(shù)和列數(shù)
• 空間復(fù)雜度：i,j指針使用常數(shù)大小額外空間