240. 搜索二维矩阵 II

发表于 更新于 分类于
240. 搜索二维矩阵 II

240. 搜索二维矩阵 II

问题描述

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

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

Example 1

1
2
输入：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

Example 2

1
2
输入：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

题解

要以矩阵的右上角作为参考点。
假设我们现在在处理matrix[x][y]
如果target > matrix[x][y]，说明必然在当前列，因为每列单调递增。所以要行数x+1，往下扫
如果target < matrix[x][y]，说明不在当前列，把列数y-1，往左一列去扫

初始条件是从第0行，第len(matrix[0])-1列开始

递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from typing import List


class Solution:

    def searchMatrixHelper(self, matrix: List[List[int]], target: int, x: int, y: int) -> bool:
        if x >= len(matrix) or y < 0:
            return False
        if matrix[x][y] == target:
            return True
        if matrix[x][y] > target:
            return self.searchMatrixHelper(matrix, target, x, y-1)
        if matrix[x][y] < target:
            return self.searchMatrixHelper(matrix, target, x+1, y)

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        return self.searchMatrixHelper(matrix, target, 0, len(matrix[0])-1)

仔细想想，其实完全没必要使用递归，直接用循环就可以了

非递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from typing import List


class Solution:

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = 0
        n = len(matrix[0])-1
        while m < len(matrix) and n >= 0:
            if matrix[m][n] == target:
                return True
            if matrix[m][n] > target:
                n -= 1
            else:
                m += 1
        return False

测试代码

1
2
3
4
5
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
solution = Solution()
print(solution.searchMatrix(matrix,target))

True

1
2
3
4
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
solution = Solution()
print(solution.searchMatrix(matrix,target))

False