題目描述：

給你一個(gè)滿足下述兩條屬性的 m x n 整數(shù)矩陣：

• 每行中的整數(shù)從左到右按非嚴(yán)格遞增順序排列。
• 每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。

給你一個(gè)整數(shù) target ，如果 target 在矩陣中，返回 true ；否則，返回 false 。

示例 1：

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
輸出：true
示例 2：

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
輸出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10⁴ <= matrix[i][j], target <= 10⁴

解題思路一：先二分查找行，再二分查找列。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        up, down = 0, m - 1
        while up <= down:
            mid = up + (down - up) // 2
            if matrix[mid][0] < target:
                up = mid + 1
            elif matrix[mid][0] > target:
                down = mid - 1
            else:
                return True
        print(matrix[up-1], target)
        left, right = 0, n - 1
        while left <= right:
            mid = left + (right - left) // 2
            if matrix[up-1][mid] < target:
                left = mid + 1
            elif matrix[up-1][mid] > target:
                right = mid - 1
            else:
                return True
        return False

# 同意
class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        col0 = [row[0] for row in matrix]
        target_row = bisect.bisect_right(col0, target) - 1
        if target_row < 0:
            return False
        target_col = bisect.bisect_left(matrix[target_row], target)
        if target_col >= N:
            return False
        if matrix[target_row][target_col] == target:
            return True
        return False

時(shí)間復(fù)雜度：O(logn + logm)
空間復(fù)雜度：O(1)

解題思路二：暴力遍歷，也能過。

class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        for i in range(M):
            for j in range(N):
                if matrix[i][j] == target:
                    return True
        return False

時(shí)間復(fù)雜度：O(nm)
空間復(fù)雜度：O(1)

解題思路三：用python的in。

class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        for i in range(M):
            if target > matrix[i][N - 1]:
                continue
            if target in matrix[i]:
                return True
        return False

時(shí)間復(fù)雜度：O(logn + m)
空間復(fù)雜度：O(1)文章來源地址http://www.zghlxwxcb.cn/news/detail-850976.html

到了這里，關(guān)于LeetCode-74. 搜索二維矩陣【數(shù)組 二分查找 矩陣】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！