0073. Set Matrix Zeroes
=======================
题目信息
--------
:题号: 0073. 矩阵置零
:难度: Medium
:主题: 矩阵、原地标记、分阶段更新
:原题: `LeetCode 0073 `_
:重点: 从保存原矩阵,推导到行列标记,再复用首行首列实现常量额外空间
题目重述
--------
给定一个 ``m × n`` 整数矩阵 ``matrix``。只要输入矩阵中的某个单元格原始值为 0,就必须把该单元格
所在的整行和整列全部设为 0。
算法必须直接修改输入矩阵,不返回新矩阵。修改过程中产生的新零不能继续触发其他行列,否则会扩大
原始零的影响范围。
约束如下:
* ``1 <= m, n <= 200``;
* ``-2^31 <= matrix[row][col] <= 2^31 - 1``;
* 进阶目标是只使用 ``O(1)`` 额外空间。
自建示例
--------
.. code-block:: text
输入:
[[1, 2, 0, 4],
[5, 6, 7, 8],
[0, 10, 11, 12]]
修改后:
[[0, 0, 0, 0],
[0, 6, 0, 8],
[0, 0, 0, 0]]
原始零位于第 0 行第 2 列和第 2 行第 0 列,因此第 0、2 行以及第 0、2 列需要清零。
.. code-block:: text
输入:
[[1, 2, 3],
[4, 0, 6],
[7, 8, 9]]
修改后:
[[1, 0, 3],
[0, 0, 0],
[7, 0, 9]]
中间的原始零只影响第 1 行和第 1 列。
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
private:
void copyAndExpand(std::vector>& matrix) {
const std::vector> original = matrix;
const int rows = static_cast(matrix.size());
const int cols = static_cast(matrix[0].size());
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (original[row][col] != 0) {
continue;
}
for (int currentCol = 0; currentCol < cols; ++currentCol) {
matrix[row][currentCol] = 0;
}
for (int currentRow = 0; currentRow < rows; ++currentRow) {
matrix[currentRow][col] = 0;
}
}
}
}
void markerArrays(std::vector>& matrix) {
const int rows = static_cast(matrix.size());
const int cols = static_cast(matrix[0].size());
std::vector zeroRow(rows, false);
std::vector zeroCol(cols, false);
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (matrix[row][col] == 0) {
zeroRow[row] = true;
zeroCol[col] = true;
}
}
}
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (zeroRow[row] || zeroCol[col]) {
matrix[row][col] = 0;
}
}
}
}
void boundaryMarkers(std::vector>& matrix) {
const int rows = static_cast(matrix.size());
const int cols = static_cast(matrix[0].size());
bool zeroFirstRow = false;
bool zeroFirstCol = false;
for (int col = 0; col < cols; ++col) {
if (matrix[0][col] == 0) {
zeroFirstRow = true;
}
}
for (int row = 0; row < rows; ++row) {
if (matrix[row][0] == 0) {
zeroFirstCol = true;
}
}
for (int row = 1; row < rows; ++row) {
for (int col = 1; col < cols; ++col) {
if (matrix[row][col] == 0) {
matrix[row][0] = 0;
matrix[0][col] = 0;
}
}
}
for (int row = 1; row < rows; ++row) {
for (int col = 1; col < cols; ++col) {
if (matrix[row][0] == 0 || matrix[0][col] == 0) {
matrix[row][col] = 0;
}
}
}
if (zeroFirstRow) {
for (int col = 0; col < cols; ++col) {
matrix[0][col] = 0;
}
}
if (zeroFirstCol) {
for (int row = 0; row < rows; ++row) {
matrix[row][0] = 0;
}
}
}
public:
void setZeroes(std::vector>& matrix) {
boundaryMarkers(matrix);
}
};
题解
----
直接扩散的污染问题
~~~~~~~~~~~~~~~~~~
扫描矩阵时若发现一个零便立即清空对应行列,后续扫描会把新写入的零误认为原始零。例如原始零只在
``(1, 1)``,清空第 1 行后,扫描到该行其他位置的新零时可能继续清空额外列。
最直接的修正是先复制完整矩阵,只根据副本中的零修改原矩阵。这样语义正确,但每个原始零都可能重新
遍历一整行和一整列,最坏时间为 ``O(mn(m+n))``,副本还需要 ``O(mn)`` 空间。
行列触发集合
~~~~~~~~~~~~
最终是否清零只取决于两个事实:当前行是否含原始零,以及当前列是否含原始零。由此可把完整副本压缩为
两个标记数组:
.. code-block:: text
zeroRow[row] = 第 row 行是否出现原始零
zeroCol[col] = 第 col 列是否出现原始零
第一次扫描只收集标记,第二次扫描再统一写零。每个位置只处理常数次,时间降为 ``O(mn)``,额外空间为
``O(m+n)``。
首行首列复用
~~~~~~~~~~~~
矩阵本身已经为每一行和每一列提供了一个可复用的存储位置:
.. code-block:: text
matrix[row][0] 作为第 row 行的清零标记
matrix[0][col] 作为第 col 列的清零标记
扫描内部区域 ``row >= 1``、``col >= 1`` 时,若遇到原始零,就把对应首列和首行位置写成 0。标记完成后,
内部单元格只需检查这两个标记槽。
边界状态分离
~~~~~~~~~~~~
``matrix[0][0]`` 同时属于首行和首列,单独一个值无法区分以下两种事实:
* 首行原本含零;
* 首列原本含零。
因此在首行首列被用作标记区之前,先用 ``zeroFirstRow`` 和 ``zeroFirstCol`` 分别保存这两个状态。两个
布尔值的数量与矩阵规模无关,仍属于 ``O(1)`` 额外空间。
分阶段更新
~~~~~~~~~~
原地方案必须按固定顺序执行:
.. code-block:: text
1. 保存首行、首列原始状态
2. 扫描内部区域并写入行列标记
3. 根据标记清零内部区域
4. 根据两个布尔值清零首行、首列
首行首列在第 3 步结束前仍承担标记作用。若提前清零边界,标记会被污染,内部区域可能全部被错误清零。
扫描不变量
~~~~~~~~~~
写标记阶段处理完内部前缀后,首列和首行中的零准确记录该前缀出现过原始零的行与列。此阶段不批量
修改内部值,因此尚未扫描的位置仍保持原始数据。
清零阶段开始时,全部触发行列已经固定。每个内部位置在且仅在其行标记或列标记为零时被改写,因此新零
不会再产生新的标记。最后恢复首行首列的独立状态,所得矩阵正好反映所有原始零的影响范围。
复杂度
~~~~~~
矩阵副本方法最坏时间为 ``O(mn(m+n))``,空间为 ``O(mn)``。行列标记数组方法时间为 ``O(mn)``,空间为
``O(m+n)``。首行首列复用方法同样为 ``O(mn)`` 时间,只使用两个布尔值,额外空间为 ``O(1)``。