Sign in Subscribe
算法

搜索二维矩阵 II

loser

• 6 min read
Share

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。

该矩阵具有以下特性：

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

示例 1：

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

示例 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

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -10^9 <= target <= 10^9

解法一（右上角阶梯搜索）：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        int row = 0;
        int col = n - 1;

        while (row < m && col >= 0)
        {
            if (matrix[row][col] == target)
            {
                return true;
            }
            else if (matrix[row][col] > target)
            {
                col--;
            }
            else
            {
                row++;
            }
        }

        return false;
    }
};

核心思想

这题的矩阵有两个方向的有序性：

  • 每一行从左到右递增
  • 每一列从上到下递增

如果只对每一行做二分，也可以查找，但没有充分利用“列也是有序的”这个条件。

更高效的做法是从右上角开始看。

右上角元素有一个很特殊的性质：

它左边的元素都比它小，它下面的元素都比它大。

所以每次比较 matrix[row][col] 和 target 时，都能直接排除一整行或者一整列。

为什么从右上角开始

假设当前站在位置 (row, col)。

由于每行从左到右升序排列，所以当前行中，当前位置左边的元素都满足：

matrix[row][j] <= matrix[row][col]

由于每列从上到下升序排列，所以当前列中，当前位置下面的元素都满足：

matrix[i][col] >= matrix[row][col]

因此：

  • 如果 matrix[row][col] > target，说明当前列从当前位置往下都大于 target，这一列可以整体排除，向左移动 col--
  • 如果 matrix[row][col] < target，说明当前行从最左边到当前位置都小于 target，这一行可以整体排除，向下移动 row++
  • 如果相等，直接返回 true

整个过程像在矩阵中走楼梯一样，所以也常叫“阶梯搜索”。

搜索区域含义

在搜索过程中，候选区域始终是：

行范围：[row, m - 1]
列范围：[0, col]

也就是说：

  • row 上面的行已经被排除
  • col 右边的列已经被排除

每走一步，候选区域都会缩小：

  • 向左走，排除一列
  • 向下走，排除一行

只要 row < m && col >= 0，候选区域还存在。

如果越界仍然没找到，就说明矩阵中不存在 target。

为什么不会漏掉答案

每次排除行或列时，都有明确的有序性作为依据。

当 matrix[row][col] > target 时：

当前列中从 row 到 m - 1 的所有元素都不小于 matrix[row][col]。

所以它们一定都大于 target，目标值不可能在这一列中。

当 matrix[row][col] < target 时：

当前行中从 0 到 col 的所有元素都不大于 matrix[row][col]。

所以它们一定都小于 target，目标值不可能在这一行中。

因此每次排除的区域都不可能包含答案。

正确性证明

我们证明：算法返回的结果满足题意。

结论 1：搜索过程中，所有未被排除的候选位置都在区域 [row, m - 1] x [0, col] 中

初始时，row = 0，col = n - 1，候选区域就是整个矩阵。

每次移动时：

  • 如果向左移动 col--，表示排除当前列
  • 如果向下移动 row++，表示排除当前行

因此候选区域始终保持为 [row, m - 1] x [0, col]。

结论 2：算法每次排除的行或列都不可能包含 target

如果 matrix[row][col] > target：

由于当前列从上到下升序排列，当前列中未被排除的元素都大于等于 matrix[row][col]。

所以这些元素都大于 target，当前列不可能包含 target。

如果 matrix[row][col] < target：

由于当前行从左到右升序排列，当前行中未被排除的元素都小于等于 matrix[row][col]。

所以这些元素都小于 target，当前行不可能包含 target。

因此算法不会错误地排除可能的答案。

结论 3：如果 target 存在，算法一定会找到它

根据结论 2，每次排除的区域都不包含 target。

所以只要 target 存在，它一定始终留在候选区域中。

算法每次都会排除一行或一列，候选区域不断缩小。

当算法访问到 target 所在位置时，会返回 true。

得出结论

如果算法返回 true，说明确实找到了某个位置满足 matrix[row][col] == target。

如果算法返回 false，说明候选区域已经为空，并且所有被排除的区域都不可能包含 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

为例。

从右上角 15 开始：

  • 15 > 5，排除最后一列，向左到 11
  • 11 > 5，继续向左到 7
  • 7 > 5，继续向左到 4
  • 4 < 5，排除第一行，向下到 5
  • 5 == 5，找到目标值，返回 true

如果 target = 20：

  • 从右上角开始不断排除行或列
  • 最终 row 或 col 越界，候选区域为空
  • 说明矩阵中不存在 20，返回 false

复杂度分析

每次循环只会发生两种移动之一：

  • col--，向左移动一列
  • row++，向下移动一行

最多向左移动 n 次，最多向下移动 m 次。

所以时间复杂度是：

O(m + n)

算法只使用了几个变量：

  • row
  • col
  • m
  • n

所以空间复杂度是：

`O(1)