LeetCode 补充题 217. 行列有序矩阵中的目标值坐标
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 240. 搜索二维矩阵 II
LeetCode 原题返回目标是否存在；本文保证目标存在且只出现一次，返回从 0 开始的行、列下标。
:::
给定每行、每列均严格递增的矩阵
matrix和目标值target。目标存在且只出现一次，返回它的行、列下标
[row, col]。
示例 1：
输入：
matrix = [[1,3],[2,4]], target = 4
输出：[1,1]
提示：
- 矩阵非空、各行等长。
- 下标从
0开始。
题意分析
行和列分别递增，但不能因此把整个矩阵展开为一维有序数组。右上角同时是当前行的最大值和当前列的最小值，比较后可以确定排除一行还是一列。
解法：右上角阶梯查找
核心思路
[!blue]
从右上角开始，当前值左边的元素更小，下方的元素更大，这让一次比较能排除一整行或一整列。
当前值大于目标时，它下方的整列也更大，所以左移一列；当前值小于目标时，它左边的整行也更小，所以向下一行。相等时已有当前位置，直接返回
[row,col]。每一步都缩小尚未排除的矩形范围，行只向下、列只向左，因此最多移动行数加列数次。
解题步骤
- 从第 0 行、最后一列开始，剩余候选位于当前位置的左下矩形。
- 当前值等于 target 时返回行、列下标。
- 当前值大于 target 时左移，排除当前剩余列；小于时下移，排除当前剩余行。
- 重复直到命中；题目保证目标存在。
代码实现
class Solution {
public int[] 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 new int[] {
row,
col
};
}
if (value > target) {
col--;
} else {
row++;
}
}
return new int[] {
-1,
-1
};
}
}
func searchMatrix(matrix [][]int, target int) []int {
row := 0
col := len(matrix[0]) - 1
for row < len(matrix) && col >= 0 {
value := matrix[row][col]
if value == target {
return []int{
row,
col,
}
}
if value > target {
col--
} else {
row++
}
}
return []int{
-1,
-1,
}
}
复杂度分析
- 时间复杂度：$O(m+n)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
从右上角开始，值偏大时排除整列，值偏小时排除整行；相等时直接返回当前坐标。
易错点总结
[!yellow]
- 从右上角出发时，大了左移，小了下移，不要把方向写反。
- 排除的是尚未搜索矩形中的行或列，已排除部分不再参与比较。
- 返回的是零基行列坐标，顺序不能颠倒。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 240. 搜索二维矩阵 II | 中等 | 都可从右上角比较并逐次排除一行或一列；该题判断是否存在，本题保证目标存在且唯一，返回行、列下标。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！