LeetCode 剑指 Offer 04. 二维数组中的查找
目录
题目描述
题意分析
给定一个 $m \times n$ 的矩阵，每一行从左到右非递减、每一列从上到下非递减，判断目标值
target是否出现在其中。题目只问「存在与否」，不要求返回下标，也不要求统计出现次数，说明中途一旦命中就可以立刻收工。
约束里透露出的信号是「行、列两个方向同时有序」。这比一维有序数组的信息更强：把矩阵摊平逐个比较是 $O(mn)$，完全没有用上有序性；只对某一行做折半查找又只用上了一半信息，行与行之间的顺序关系被浪费了。真正值得追问的是：能不能让一次比较就否定掉一整行或一整列。
需要留意的边界情形有四类：矩阵本身是空数组；矩阵有行但行内没有元素；
target比全表最小值还小或比最大值还大；矩阵中存在重复值。
解法：右上角阶梯搜索
核心思路
问题关键：要同时利用行、列有序，让一次比较排除整行或整列。右上角既是当前行最大值，又是当前列最小值，比较后的移动方向唯一；左上角和右下角都无法做到这一点。
为什么选阶梯搜索：从右上角开始，当前值大于
target就排除当前列，小于target就排除当前行。相比 $O(mn)$ 扫描和 $O(m\log n)$ 逐行二分，它把两个方向的有序性都利用起来，且只需常数空间。左下角出发是完全对称的替代方案。循环不变量：每轮开始时，若答案存在，它一定在候选矩形
[row..m-1] × [0..col]中。正确性：若当前值大于目标，该列从当前行向下的值都不小于当前值，因此整列不可能命中；若当前值小于目标，该行从左到当前列的值都不大于当前值，因此整行不可能命中。每次只删除不含答案的区域，不变量始终成立；命中时返回
true，候选矩形为空时返回false，两种结论都正确。
解题步骤
- 空矩阵或首行为空时返回
false，避免访问matrix[0]越界。- 指针放在右上角：
row = 0，col = n - 1。- 当前值等于目标时返回
true；大于目标时左移一列；小于目标时下移一行。row == m或col < 0时候选区域已空，返回false。口述样例：对
[[1,4,7],[2,5,8],[3,6,9]]查找5，访问路径是7 → 4 → 5：7太大删列，4太小删行，随后命中。
代码实现
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col--;
} else {
row++;
}
}
return false;
}
}
func findNumberIn2DArray(matrix [][]int, target int) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}
row := 0
col := len(matrix[0]) - 1
for row < len(matrix) && col >= 0 {
if matrix[row][col] == target {
return true
} else if matrix[row][col] > target {
col--
} else {
row++
}
}
return false
}
复杂度分析
- 时间复杂度：$O(m + n)$。行指针最多下移 $m$ 次，列指针最多左移 $n$ 次。
- 空间复杂度：$O(1)$，只维护两个下标。
关键点总结
- 选择一维最大、另一维最小的角，比较结果才没有歧义。
- 候选矩形是不变量；每轮严格缩小一个维度，因此算法一定终止。
- 左下角同样可行，移动规则与右上角对称。
- 本题不满足“上一行末尾小于下一行开头”，不能把矩阵直接摊平二分。
易错点总结
- 空判断必须先看外层，再访问
matrix[0]；[]和[[]]都要覆盖。- 列下标应由
matrix[0].length初始化，不能把行数当列数；非方阵会暴露该错误。- 右上角“大于左移、小于下移”，方向写反会删除仍可能含答案的区域。
- 不能从左上角开始：例如
[[1,4],[2,5]]查4，看到1 < 4时右移和下移都有可能，无法安全排除整行或整列。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 74. 搜索二维矩阵 | 中等 | 每行首元素大于上一行末元素，摊平后全局有序，可把一维下标映射成二维直接折半，不需要阶梯搜索 |
| 240. 搜索二维矩阵 II | 中等 | 与本题条件完全一致的英文版，可顺带练习按中心元素切分的分治写法 |
| 面试题 10.09. 排序矩阵查找 | 中等 | 同样的阶梯搜索，但要求返回命中坐标而不只是布尔值，命中时要保存 row 与 col
|
| 378. 有序矩阵中第 K 小的元素 | 中等 | 同样的行列有序前提，但求第 $k$ 小，需要对数值域折半并用阶梯走法统计不超过某值的个数 |
| 4. 寻找两个正序数组的中位数 | 困难 | 同为「每步排除一批候选」的思路，但作用在两条一维序列的切分点上，不变量更难维护 |
| 33. 搜索旋转排序数组 | 中等 | 有序性被旋转破坏，需要先判断哪一半仍然单调再决定收缩方向 |