题目描述

[EN | CN]

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

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

示例:

现有矩阵 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。

解法 1:从左下角 / 右上角出发

题目给出的二维数组是从左到右、从上到下都是递增的,如果我们从数组 左上角(即 [0, 0])开始遍历,那么每一步都有 3 个方向可选,并且必定有 2 个方向是同增或者同减 ,不便于搜寻。事实上,我们可以从数组的 右上角(即 [0, n - 1])出发,那么每走一步的选择只有两种可能(往左或者往下),逻辑跟实现都简单很多。当然也可以选择从左下角(即 [m - 1, 0])出发。

为什么这种情况下只有 2 种可能?假设我们从右上角出发,若当前值小于 target,则排除当前行,若当前值大于 target,则排除当前列。因此每次走一步,都会排除当前行或列,并且排除掉的只有可能是最上端的行或者最右端的列!

假设二维数组的宽高分别为 $m$、$n$,那么

  • 时间复杂度为 $O(m + n)$,总是要遍历;
  • 空间复杂度为 $O(1)$,不需要额外空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0:
            return False

        num_rows = len(matrix)
        num_cols = len(matrix[0])

        i, j = 0, num_cols - 1
        while i < num_rows and j > -1:
            if matrix[i][j] < target:
                i += 1
            elif matrix[i][j] > target:
                j -= 1
            else:
                return True

        return False
  • Runtime: 28 ms, faster than 99.83% of Python3 online submissions for Search a 2D Matrix II.
  • Memory Usage: 17.4 MB, less than 92.59% of Python3 online submissions for Search a 2D Matrix II.