0074. Search a 2D Matrix
========================
题目信息
--------
:题号: 0074. 搜索二维矩阵
:难度: Medium
:主题: 矩阵、二分查找、坐标映射
:原题: `LeetCode 0074 `_
:重点: 从逐格扫描,推导到定位候选行,再把矩阵视为虚拟一维有序序列
题目重述
--------
给定一个 ``m × n`` 整数矩阵 ``matrix`` 和整数 ``target``,判断目标值是否存在于矩阵中。
矩阵满足以下条件:
* 每一行都按非递减顺序排列;
* 每一行的第一个元素都严格大于上一行的最后一个元素。
算法必须达到 ``O(log(m * n))`` 时间复杂度。
约束为 ``1 <= m, n <= 100``,``-10^4 <= matrix[i][j], target <= 10^4``。
自建示例
--------
.. code-block:: text
输入:
matrix = [[2,4,8],
[12,15,19],
[25,31,40]]
target = 15
输出:true
按行连接后得到 ``[2,4,8,12,15,19,25,31,40]``,目标值位于虚拟下标 4。
.. code-block:: text
输入:
matrix = [[1,3,3],
[7,9,12]]
target = 5
输出:false
行内允许重复值,但第一行末尾的 3 仍小于第二行开头的 7;5 位于两行取值范围之间。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
bool linearScan(const std::vector>& matrix, int target) {
for (const auto& row : matrix) {
for (int value : row) {
if (value == target) {
return true;
}
}
}
return false;
}
bool rowThenColumnBinary(
const std::vector>& matrix,
int target
) {
int rows = static_cast(matrix.size());
int left = 0;
int right = rows - 1;
int candidate = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (matrix[mid][0] <= target) {
candidate = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
if (candidate == -1) {
return false;
}
const auto& row = matrix[candidate];
return std::binary_search(row.begin(), row.end(), target);
}
bool flattenedBinary(
const std::vector>& matrix,
int target
) {
int rows = static_cast(matrix.size());
int cols = static_cast(matrix[0].size());
int left = 0;
int right = rows * cols - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int row = mid / cols;
int col = mid % cols;
int value = matrix[row][col];
if (value == target) {
return true;
}
if (value < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
public:
bool searchMatrix(std::vector>& matrix, int target) {
return flattenedBinary(matrix, target);
}
};
题解
----
逐格扫描
~~~~~~~~
直接检查所有元素一定能找到目标,但最坏需要访问 ``m * n`` 个位置,时间为 ``O(mn)``,没有利用矩阵的有序性。
两层有序结构
~~~~~~~~~~~~
每一行内部非递减,并且下一行首元素严格大于上一行末元素。因此目标若存在,只可能位于最后一个满足
``matrix[row][0] <= target`` 的行。
先在各行首元素中寻找这个最后可行行,再在该行内部二分,时间为:
.. code-block:: text
O(log m + log n)
若目标小于第一行首元素,则不存在候选行。若候选行中也没有目标,其他行更不可能包含目标。
虚拟一维序列
~~~~~~~~~~~~
把矩阵按行连接,可得到一个全局非递减序列。无需真的复制元素,只需把虚拟下标映射回二维坐标。
设列数为 ``cols``,虚拟下标 ``index`` 对应:
.. code-block:: text
row = index / cols
col = index % cols
整数商表示已经跨过的完整行数,余数表示当前行中的列下标。区间 ``0..m*n-1`` 与矩阵中的所有位置一一对应。
闭区间二分
~~~~~~~~~~
``[left, right]`` 保存所有尚未排除的虚拟位置。读取中点后有三种情况:
* 中点值等于目标,立即返回;
* 中点值小于目标,中点及其左侧全部排除;
* 中点值大于目标,中点及其右侧全部排除。
每轮都把边界移动到 ``mid + 1`` 或 ``mid - 1``,候选区间严格缩小。
状态跟踪
~~~~~~~~
对示例矩阵搜索 ``20``:
.. list-table::
:header-rows: 1
* - 区间
- 中点
- 中点值
- 下一步
* - ``0..8``
- 4
- 15
- 左边界变为 5
* - ``5..8``
- 6
- 25
- 右边界变为 5
* - ``5..5``
- 5
- 19
- 左边界变为 6
此时 ``left > right``,所有位置都已排除。
跨行边界
~~~~~~~~
上一行末元素严格小于下一行首元素,所以虚拟序列在换行处仍保持有序。行内即使出现重复值,也不会破坏二分所需的非递减性质。
两种二分的关系
~~~~~~~~~~~~~~
两阶段方法显式利用“行首有序”和“行内有序”;虚拟展平方法把这两层顺序合并为一个长度为 ``m*n`` 的有序区间。
两阶段方法时间为 ``O(log m + log n)``,虚拟展平方法时间为 ``O(log(mn))``。两者等价,因为:
.. code-block:: text
log(mn) = log m + log n
虚拟展平只维护一个二分区间,公开入口采用该方法。
复杂度
~~~~~~
线性扫描时间 ``O(mn)``。两阶段二分和虚拟展平二分时间均为 ``O(log(mn))``,额外空间均为 ``O(1)``。