LeetCode 面试题 10.09. 排序矩阵查找
题目描述
题意分析
矩阵每一行从左到右、每一列从上到下都有序，判断目标值是否存在。题目没有保证上一行末尾小于下一行开头，所以不能把整个矩阵直接展平成一个全局有序数组做二分。
逐元素扫描是 $O(mn)$；逐行二分是 $O(m \log n)$，只利用了行有序。题目同时给出列有序，意味着可以从一个同时具有两个方向单调性的角落出发，每次比较排除一整行或一整列。
空矩阵或空行应返回
false。重复值不影响算法，因为只需判断存在性，不需要定位第一个位置。
解法：从右上角阶梯搜索
核心思路
[!blue]
用
row、col表示当前候选矩形的右上角，最初为(0, n - 1)。未排除的区域是[row, m) × [0, col]：当前位置是这一行剩余部分的最大值，也是这一列剩余部分的最小值，因此一次比较就能排除一整行或一整列：
- 当前值大于
target：当前列从这里往下的值都不小于它，剩余列中没有目标，令col--。- 当前值小于
target：当前行从这里往左的值都不大于它，剩余行中没有目标，令row++。- 相等：直接返回
true。初始候选矩形包含整个矩阵，每一步删掉的部分又都不可能含有目标，因此始终保持：若目标存在，它必在当前候选矩形中。命中时直接返回；
row == m或col < 0时，候选矩形已经为空，便可确定目标不存在。两个指针只向下或向左移动，不会重新访问已排除的行列。每次未命中都严格缩小候选区域，所以搜索必然结束，总移动次数至多为
m + n。
解题步骤
- 判空后令
row = 0、col = matrix[0].length - 1，定位右上角。- 当
row < m且col >= 0时比较matrix[row][col]与目标。- 大于目标就
col--，小于目标就row++，相等立即成功。- 行越过底部或列越过左侧仍未命中，返回
false。空矩阵时先返回，才能安全读取首行长度；首行为空时也直接返回。只有一行或一列时，候选区域与移动规则仍然成立，无需单独实现。相等值不会被大小比较误删，第一次遇到目标即可结束。
代码实现
// 候选区域始终是左下方矩形，每步排除一行或一列。
class Solution {
public boolean searchMatrix(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) {
int current = matrix[row][col];
if (current == target) {
return true;
}
if (current > target) {
col--;
} else {
row++;
}
}
return false;
}
}
// 候选区域始终是左下方矩形，每步排除一行或一列。
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}
row, col := 0, len(matrix[0])-1
for row < len(matrix) && col >= 0 {
current := matrix[row][col]
if current == target {
return true
}
if current > target {
col--
} else {
row++
}
}
return false
}
复杂度分析
- 时间复杂度：$O(m+n)$。行指针最多向下移动
m次，列指针最多向左移动n次，二者都不回退。- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 右上角和左下角的两个可走方向大小变化相反；左上角向右、向下都增大，右下角向左、向上都减小，无法按同一规则唯一决定删行还是删列。
- 面试时应先区分本题与 74：本题只保证行列分别有序，不能展平二分；阶梯搜索才同时使用两维单调性。
- 正确性表达围绕候选矩形不变量：大就删列，小就删行，每次删掉的区域都不可能含目标。
- 逐行二分也能通过，但复杂度 $O(m\log n)$，在矩阵接近方阵时不如 $O(m+n)$，且浪费了列有序条件。
易错点总结
[!yellow]
- 把矩阵直接展平二分：行末与下一行开头没有整体顺序保证，展平后未必有序。
- 当前值大时向下、小时向左：方向完全反了，候选值只会离目标更远。大要左移，小要下移。
- 循环条件用
row < m || col >= 0：任一坐标越界后仍继续访问，产生数组越界；必须同时合法。- 未处理空矩阵就读取第一行长度：
matrix = []会直接越界，应在入口判空。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 74. 搜索二维矩阵 | 中等 | 原题额外保证行与行整体有序，可以展平二分，本题只能依赖行列分别有序。 |
| 378. 有序矩阵中第 K 小的元素 | 中等 | 同样利用行列有序矩阵的单调性，原题寻找第k小值，可用阶梯计数配合值域二分。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！