PeterQwQ
0%

Leetcode 240 搜索二维矩阵 II

发表于 更新于

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

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

对于这样性质的矩阵，我们从右上角开始搜索，如果当前元素比目标值大，那么向左移动一列，如果当前元素比目标值小，那么向下移动一行。这样可以保证每次移动都能够排除一行或者一列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        if target < matrix[0][0]:
            return False
        if target > matrix[m-1][n-1]:
            return False
        
        i, j = 0, n-1
        while i < m and j >= 0:
            right_top = matrix[i][j]
            if target == right_top:
                return True
            if target < right_top:
                j -= 1
            else:
                i += 1
        return False