0240. Search a 2D Matrix II¶
题目信息¶
- 题号:
0240
- 难度:
Medium
- 主题:
矩阵、单调性、二分查找、搜索
- 原题:
- 重点:
每行与每列分别非递减、目标存在性、重复值、矩阵不要求整体展平有序
题目重述¶
给定一个 m x n 的整数矩阵 matrix 和整数 target。矩阵的每一行都从左到右按非递减顺序排列,每一列都从上到下按非递减顺序排列。判断矩阵中是否至少有一个单元格的值等于 target;存在时返回 true,否则返回 false。
m 和 n 均位于 [1, 300],矩阵元素和 target 位于 [-10^9, 10^9]。相邻行之间没有“上一行末尾小于下一行开头”的额外保证,因此不能把矩阵直接视为一个整体有序的一维数组。矩阵可以包含重复值,函数无需修改输入。
自建示例¶
目标位于内部位置:
输入:matrix = [[1, 4, 8, 11],
[2, 5, 9, 14],
[6, 7, 12, 18]],target = 7
输出:true
解释:第 3 行第 2 列的值为 7,满足目标存在性要求。
目标落在两个已有值之间:
输入:matrix = [[1, 3, 6],
[2, 5, 9]],target = 4
输出:false
解释:所有行列都保持非递减,但矩阵中没有值 4。
从右上角消除一行或一列¶
从右上角 (row=0, column=n-1) 开始:
当前值等于
target,立即成功;当前值大于
target,当前列下面的值只会更大,整列都不可能包含目标,向左移动;当前值小于
target,当前行左侧的值只会更小,整行都不可能包含目标,向下移动。
每次移动至少删除一行或一列的搜索范围,直到越过矩阵边界。矩阵的行列单调性足以支持这个消除过程, 但不要求行与行之间整体有序,因此不应把坐标直接映射到一维二分查找。
正确性说明¶
若当前值大于目标,因为当前列从上到下非递减,当前位置下方不可能出现更小的目标,删除整列安全; 若当前值小于目标,因为当前行从左到右非递减,当前位置左侧不可能出现更大的目标,删除整行安全。 等于时返回真。每个未删除位置都保留了出现目标的可能性,越界时搜索范围为空,返回假也就正确。
C++ 实现¶
class Solution {
public:
bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int row = 0;
int column = static_cast<int>(matrix[0].size()) - 1;
const int rows = static_cast<int>(matrix.size());
while (row < rows && column >= 0) {
if (matrix[row][column] == target) return true;
if (matrix[row][column] > target) {
--column;
} else {
++row;
}
}
return false;
}
};
代码分析¶
行指针只向下移动,列指针只向左移动,最多执行 m+n 次比较,时间复杂度为 O(m+n),
额外空间为 O(1)。算法只读取矩阵,不受重复值影响,也不需要额外的 visited 标记。