LeetCode 第 240 题：搜索二维矩阵 II

字数 2391 2025-10-27 21:43:38

LeetCode 第 240 题：搜索二维矩阵 II

题目描述
给定一个 m x n 的矩阵 matrix 和一个目标值 target。该矩阵具有以下特性：

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

请编写一个高效的算法来搜索矩阵中是否存在目标值 target。如果存在，返回 true；否则，返回 false。

解题过程

第一步：理解问题与数据特性
这个问题的核心在于利用矩阵独特的排序规律，而不是简单地将其视为一个无序的二维数组进行暴力搜索。暴力搜索的时间复杂度是 O(m * n)，这不是我们想要的。
关键特性是：

行有序：每一行都是一个递增的序列。
列有序：每一列也是一个递增的序列。

这个特性意味着矩阵在某种程度上是“全局”有序的。例如，左上角是整个矩阵的最小值，右下角是整个矩阵的最大值。但请注意，它并不是一个完全标准的二叉搜索树，因为从左上角到右下角的对角线上的元素并非严格有序。

第二步：寻找高效的搜索起点
既然矩阵是有序的，我们自然会想到二分查找。我们可以对每一行进行二分查找，时间复杂度是 O(m * log n)，这比暴力法好，但我们可以做得更好。

我们需要一个能同时利用“行有序”和“列有序”这两个条件的搜索路径。观察矩阵，我们会发现几个特殊的“角落”位置：

左上角 (0, 0)：这是最小值。如果我们从这里开始，无论向右还是向下移动，元素都会变大。如果 target 比当前值大，我们有两个方向（右、下）都可以选择，这会产生歧义。
右下角 (m-1, n-1)：这是最大值。同样，如果从这里开始向左或向上移动，元素都会变小。如果 target 比当前值小，我们也有两个方向（左、上）可以选择，同样会产生歧义。
左下角 (m-1, 0)：这是这一行的最小值，同时也是这一列的最大值。从这个点开始：
- 如果 target 比当前值小，那么由于当前元素是这一列的最大值，target 绝不可能出现在这一列（因为这一列的所有其他元素都比它小）。所以，我们可以安全地向上移动一行（即 row--），排除一整列。
- 如果 target 比当前值大，那么由于当前元素是这一行的最小值，target 绝不可能出现在这一行（因为这一行的所有其他元素都比它大）。所以，我们可以安全地向右移动一列（即 col++），排除一整行。
右上角 (0, n-1)：与左下角对称。这是这一行的最大值，同时也是这一列的最小值。
- 如果 target 比当前值小，那么可以向左移动一列（col--），排除当前行。
- 如果 target 比当前值大，那么可以向下移动一行（row++），排除当前列。

从左下角或右上角开始，我们每一步移动都能确定性地排除一行或一列，从而将搜索空间快速缩小。

第三步：算法步骤（以从右上角开始为例）

初始化：将起始点设置在矩阵的右上角，即 row = 0, col = n - 1。
循环搜索：在索引不越界（即 row < m 且 col >= 0）的条件下，进行循环比较：
a. 比较当前矩阵元素 matrix[row][col] 和目标值 target。
b. 如果 matrix[row][col] == target，恭喜你，找到了！立即返回 true。
c. 如果 target 小于 matrix[row][col]：
* 解释：因为当前元素是这一列的最小值（由于列是向下递增的），所以 target 如果比这个最小值还小，那么它绝对不可能出现在这一列的任何位置。
* 操作：因此，我们可以将整个这一列排除掉。执行 col--（即向左移动一列）。
d. 如果 target 大于 matrix[row][col]：
* 解释：因为当前元素是这一行的最大值（由于行是向右递增的），所以 target 如果比这个最大值还大，那么它绝对不可能出现在这一行的任何位置。
* 操作：因此，我们可以将整个这一行排除掉。执行 row++（即向下移动一行）。
终止条件：如果循环结束（即行或列索引越界）还没有找到 target，说明 target 不在矩阵中，返回 false。

第四步：举例说明
假设矩阵 matrix 如下，我们要查找 target = 5：

[ [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] ]

起点在右上角 (0,4)，值是 15。
- 5 < 15，所以向左移动一列，排除最右边一整列。现在位置是 (0,3)，值是 11。
(0,3) 的值是 11。
- 5 < 11，继续向左移动一列。现在位置是 (0,2)，值是 7。
(0,2) 的值是 7。
- 5 < 7，继续向左移动一列。现在位置是 (0,1)，值是 4。
(0,1) 的值是 4。
- 5 > 4，所以向下移动一行，排除第一行。现在位置是 (1,1)，值是 5。
(1,1) 的值是 5，等于 target，搜索成功，返回 true。

搜索路径像一个“阶梯”一样，从右上角向左下角移动。

第五步：复杂度分析

时间复杂度：O(m + n)。在最坏的情况下，我们从右上角走到左下角，最多会走 m 行 + n 列的距离。这比 O(m * n) 和 O(m * log n) 都要高效得多。
空间复杂度：O(1)。我们只使用了几个固定的变量（row, col），没有使用额外的数据结构。

这个算法的精髓在于选择了一个正确的起点（右上角或左下角），使得每次比较都能线性地缩小搜索范围，从而实现了高效查找。

LeetCode 第 240 题：搜索二维矩阵 II 题目描述给定一个 m x n 的矩阵 matrix 和一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。请编写一个高效的算法来搜索矩阵中是否存在目标值 target。如果存在，返回 true；否则，返回 false。解题过程第一步：理解问题与数据特性这个问题的核心在于利用矩阵独特的排序规律，而不是简单地将其视为一个无序的二维数组进行暴力搜索。暴力搜索的时间复杂度是 O(m * n)，这不是我们想要的。关键特性是：行有序：每一行都是一个递增的序列。列有序：每一列也是一个递增的序列。这个特性意味着矩阵在某种程度上是“全局”有序的。例如，左上角是整个矩阵的最小值，右下角是整个矩阵的最大值。但请注意，它并不是一个完全标准的二叉搜索树，因为从左上角到右下角的对角线上的元素并非严格有序。第二步：寻找高效的搜索起点既然矩阵是有序的，我们自然会想到二分查找。我们可以对每一行进行二分查找，时间复杂度是 O(m * log n)，这比暴力法好，但我们可以做得更好。我们需要一个能同时利用“行有序”和“列有序”这两个条件的搜索路径。观察矩阵，我们会发现几个特殊的“角落”位置：左上角 (0, 0) ：这是最小值。如果我们从这里开始，无论向右还是向下移动，元素都会变大。如果 target 比当前值大，我们有两个方向（右、下）都可以选择，这会产生歧义。右下角 (m-1, n-1) ：这是最大值。同样，如果从这里开始向左或向上移动，元素都会变小。如果 target 比当前值小，我们也有两个方向（左、上）可以选择，同样会产生歧义。左下角 (m-1, 0) ：这是这一行的最小值，同时也是这一列的最大值。从这个点开始：如果 target 比当前值小，那么由于当前元素是这一列的最大值， target 绝不可能出现在这一列（因为这一列的所有其他元素都比它小）。所以，我们可以安全地向上移动一行（即 row-- ），排除一整列。如果 target 比当前值大，那么由于当前元素是这一行的最小值， target 绝不可能出现在这一行（因为这一行的所有其他元素都比它大）。所以，我们可以安全地向右移动一列（即 col++ ），排除一整行。右上角 (0, n-1) ：与左下角对称。这是这一行的最大值，同时也是这一列的最小值。如果 target 比当前值小，那么可以向左移动一列（ col-- ），排除当前行。如果 target 比当前值大，那么可以向下移动一行（ row++ ），排除当前列。从左下角或右上角开始，我们每一步移动都能确定性地排除一行或一列，从而将搜索空间快速缩小。第三步：算法步骤（以从右上角开始为例）初始化：将起始点设置在矩阵的右上角，即 row = 0 , col = n - 1 。循环搜索：在索引不越界（即 row < m 且 col >= 0 ）的条件下，进行循环比较： a. 比较当前矩阵元素 matrix[row][col] 和目标值 target 。 b. 如果 matrix[row][col] == target ，恭喜你，找到了！立即返回 true 。 c. 如果 target 小于 matrix[row][col] ： * 解释：因为当前元素是这一列的最小值（由于列是向下递增的），所以 target 如果比这个最小值还小，那么它绝对不可能出现在这一列的任何位置。 * 操作：因此，我们可以将整个这一列排除掉。执行 col-- （即向左移动一列）。 d. 如果 target 大于 matrix[row][col] ： * 解释：因为当前元素是这一行的最大值（由于行是向右递增的），所以 target 如果比这个最大值还大，那么它绝对不可能出现在这一行的任何位置。 * 操作：因此，我们可以将整个这一行排除掉。执行 row++ （即向下移动一行）。终止条件：如果循环结束（即行或列索引越界）还没有找到 target ，说明 target 不在矩阵中，返回 false 。第四步：举例说明假设矩阵 matrix 如下，我们要查找 target = 5 ：起点在右上角 (0,4) ，值是 15 。 5 < 15 ，所以向左移动一列，排除最右边一整列。现在位置是 (0,3) ，值是 11 。 (0,3) 的值是 11 。 5 < 11 ，继续向左移动一列。现在位置是 (0,2) ，值是 7 。 (0,2) 的值是 7 。 5 < 7 ，继续向左移动一列。现在位置是 (0,1) ，值是 4 。 (0,1) 的值是 4 。 5 > 4 ，所以向下移动一行，排除第一行。现在位置是 (1,1) ，值是 5 。 (1,1) 的值是 5 ，等于 target ，搜索成功，返回 true 。搜索路径像一个“阶梯”一样，从右上角向左下角移动。第五步：复杂度分析时间复杂度：O(m + n)。在最坏的情况下，我们从右上角走到左下角，最多会走 m 行 + n 列的距离。这比 O(m * n) 和 O(m * log n) 都要高效得多。空间复杂度：O(1)。我们只使用了几个固定的变量（ row , col ），没有使用额外的数据结构。这个算法的精髓在于选择了一个正确的起点（右上角或左下角），使得每次比较都能线性地缩小搜索范围，从而实现了高效查找。