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