LeetCode 剑指 Offer 04. 二维数组中的查找
题目描述
题意分析
二维矩阵的每一行从左到右有序，每一列从上到下有序，判断给定目标值是否出现，返回布尔值。矩阵可以不是方阵，行数与列数要分别处理。
题目只保证行内和列内的大小顺序，不保证上一行末尾小于下一行开头，因此按行拼成一维数组后未必有序，不能直接对整个展开结果二分。空矩阵或没有列时，目标不存在。
解法：右上角阶梯搜索
核心思路
[!blue]
从右上角开始，当前元素同时是候选区域第一行的最大值和最后一列的最小值。这两个方向的大小关系相反，比较目标后就能确定排除哪一整条边界，而不是猜测应该往哪里走。
用
row、col表示当前右上角，尚未排除的区域是第row行到最后一行、第0列到第col列。若当前值大于目标，它下方同列元素都不小于当前值，也不可能是目标，因此这一整列都可以删除，令col--。若当前值小于目标，它左侧同行元素都不大于当前值，同样不可能命中，因此这一整行都可以删除，令
row++。若等于目标则立即成功。每种删除都只排除已证明不含目标的位置，剩余区域仍然是行列有序的矩形，因此可以重复同样的判断。每一步至少减少一行或一列，游标只会向左、向下移动。越过最左列或最后一行时，候选区域已经为空，可以确定不存在目标。从左下角出发也具有对称的排除关系；左上角则同时小于右侧和下方元素，无法仅凭一次比较确定删除哪一边。
解题步骤
- 先检查外层行数，再检查首行列数；任意一个为零都返回
false。- 令
row = 0、col = 列数 - 1，从右上角开始。- 当前位置等于目标时返回
true；大于目标时删除当前列、向左移动，小于目标时删除当前行、向下移动。- 只要行列下标仍在候选范围内就继续比较，越界后返回
false。
代码实现
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)$，只维护行、列两个下标。
关键点总结
[!green]
- 选右上角是为了同时获得“左边更小”和“下面更大”的明确关系。
- 每次比较排除一整行或一整列，并保持候选区域仍为矩形。
- 只删除不可能命中的边界，既保证不漏解，也保证单向移动能够结束。
- 行列分别有序与整个数组展开后有序是不同条件，不能混用搜索方法。
易错点总结
[!yellow]
- 先读取
matrix[0]再判断外层是否为空，空矩阵会直接越界。- 用行数初始化列下标，只在部分方阵输入上碰巧正确，非方阵会出错。
- 把“大于目标左移、小于目标下移”写反，会删除仍可能包含答案的区域。
- 从左上角遇到小于目标就随意选一个方向，不能证明另一个方向没有答案。
- 直接展开成一维二分，额外假设了题目没有提供的跨行全局顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 74. 搜索二维矩阵 | 中等 | 原题额外保证行与行整体有序，可以展平二分，本题只能依靠行列分别有序。 |
| 378. 有序矩阵中第 K 小的元素 | 中等 | 同样利用行列单调性，原题可通过阶梯计数与值域二分寻找第k小值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！