搜索二维矩阵 II（LeetCode）

题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

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

解题

"""
时间复杂度为 O(m + n)，其中 m 是矩阵的行数，n 是矩阵的列数。
"""


def searchMatrix(matrix, target) -> bool:
    if not matrix or not matrix[0]:
        return False

    # 从右上角开始搜索
    row, col = 0, len(matrix[0]) - 1

    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1  # 如果当前值大于目标值，向左移动
        else:
            row += 1  # 如果当前值小于目标值，向下移动

    return False


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
print(searchMatrix(matrix, target))