LeetCode 240. 搜索二维矩阵 II
题目描述
题意分析
矩阵的每一行从左到右有序，每一列从上到下有序，要求判断目标值是否存在，返回布尔值。
行列分别有序，不代表把矩阵按行拼成一维数组后也有序：下一行的首元素不一定大于上一行的末元素，所以不能直接对整个展开数组做二分。矩阵也不要求是正方形，行数和列数需要分别处理。
解法：从右上角阶梯式搜索
核心思路
[!blue]
要在一次比较后排除一批位置，当前元素必须同时能代表某一行的最大值和某一列的最小值。右上角正好满足：向左只会变小，向下只会变大，因此目标偏大或偏小时有明确的排除方向。
设当前位于
(row, col)，仍有可能包含目标的区域是行row..m - 1、列0..col组成的矩形。当前位置是这个区域顶行的最大值，也是最右列的最小值。若当前值大于目标，那么当前列中剩余的值都不小于它，也都大于目标，整列可以排除，令
col--。若当前值小于目标，那么当前行中剩余的值都不大于它，也都小于目标，整行可以排除，令row++。相等时则直接找到答案。每次只删除已经证明不可能含目标的行或列，所以目标若存在，就一直留在剩余矩形中。新的右上角仍有同样的行列关系，可以重复这一判断；行或列越界时，候选区域已经为空，才能确定目标不存在。
解题步骤
- 初始化
row = 0、col = 列数 - 1，从矩阵右上角出发。- 当
row < 行数且col >= 0时，读取当前值并与目标比较。- 若相等，返回
true；若偏大，左移一列；若偏小，下移一行。- 任一边界越界后，说明剩余候选区域为空，返回
false。
代码实现
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
int value = matrix[row][col];
if (value == target) {
return true;
}
if (value > target) {
// 当前列下方只会更大，目标更小时整列都可排除。
col--;
} else {
// 当前行左方只会更小，目标更大时整行都可排除。
row++;
}
}
return false;
}
}
func searchMatrix(matrix [][]int, target int) bool {
row := 0
col := len(matrix[0]) - 1
for row < len(matrix) && col >= 0 {
value := matrix[row][col]
if value == target {
return true
}
if value > target {
// 当前列下方只会更大，目标更小时整列都可排除。
col--
} else {
// 当前行左方只会更小，目标更大时整行都可排除。
row++
}
}
return false
}
复杂度分析
设矩阵有
m行、n列。
- 时间复杂度：$O(m+n)$，每次比较都向左或向下走一步，最多检查
m + n - 1个位置。- 空间复杂度：$O(1)$，只记录当前位置和当前值。
关键点总结
[!green]
- 右上角一侧变小、一侧变大，能够根据比较结果唯一确定要删除的边界。
- 指针移动只是表现，正确性来自整行或整列都已被有序性排除。
- 剩余矩形一直包含所有可能答案，因此越界代表搜索空间耗尽，而不是随意终止。
易错点总结
[!yellow]
- 当前值过大时向下走，只会进入更大的区域，应当排除当前列并左移。
- 从左上角开始，当前值过小时右方和下方都可能存在答案，无法据此排除一整行或列。
- 用行数初始化列下标，会在非方阵中漏列或越界；列边界应取
matrix[0].length - 1。- 循环缺少任一边界检查，目标不在矩阵内时就可能越界访问。
- 对按行展开的数组做整体二分，依赖了本题没有保证的跨行顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 74. 搜索二维矩阵 | 中等 | 原题额外保证行与行整体有序，可以展平二分，本题只能依靠行列分别有序。 |
| 378. 有序矩阵中第 K 小的元素 | 中等 | 同样利用行列单调性，原题可通过阶梯计数与值域二分寻找第k小值。 |
| 补充题 217. 行列有序矩阵中的目标值坐标 | 中等 | 都从矩阵一角出发，利用行列有序性缩小范围；补充题返回坐标而非布尔值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！