73. 矩阵置零（中等）

Blind 75 › 73. 矩阵置零（中等） （第 3 章）
文章工具

题目

给定一个 m 行 n 列的整数矩阵。若某个位置的值是 0，就把它所在的整行、整列都改成 0；所有 0 同时生效，最终要求原地修改，不返回新矩阵。

换句话说：先找出原矩阵里所有 0，再把这些 0 所在的行、列统一清零；不能边找边清，因为新产生的 0 会继续扩散。

自造示例：[[3,1,2,4],[5,0,7,8],[1,1,1,1],[9,3,1,6]] → [[3,0,2,4],[0,0,0,0],[1,0,1,1],[9,0,1,6]]

约束：1 ≤ m, n ≤ 200；元素为 32 位整数，范围 -231 ~ 231 - 1；进阶要求额外空间 O(1)。

思路

一句话：把“哪些行、哪些列要清零”记下来，再统一清零；最高明的记法，是把标记写进矩阵自己的第 0 行和第 0 列。

最直白的做法：复制一张同大的标记矩阵，第一趟标出哪些格子原本是 0，第二趟按标记把对应行列清零。时间 O(mn)，但要额外开整张矩阵，空间 O(mn)，浪费。

改进一：不用整张标记矩阵，只记“哪一行、哪一列需要清”，开两个数组 row[m]、col[n]。第一趟扫到 matrix[i][j] == 0 就把 row[i]、col[j] 置真；第二趟按数组统一清零。空间降到 O(m + n)，但提示说还可以更好。

关键观察：row、col 这两个数组加起来正好是 m + n 个格子，而矩阵自己的第 0 行、第 0 列恰好也有 m + n 个格子。把它们拿来当标记数组用：内部某格 (i, j) 为 0，就写 matrix[i][0] = 0、matrix[0][j] = 0。这样额外空间从 O(m + n) 降到 O(1)。

代价是必须先花两个布尔变量，单独记住第 0 行、第 0 列本身是否含 0——否则它们一旦被当成标记，原始信息就丢了。同时必须“先标记、后清零”两趟完成，边扫边清会让新产生的 0 像传染一样扩散。

解法

四步，全程原地：

  1. 扫描第 0 行、第 0 列，分别记下 firstRowZero、firstColZero 两个布尔。
  2. 扫描内部区域（i ≥ 1, j ≥ 1），遇 0 就把 matrix[i][0] 和 matrix[0][j] 置 0，作为标记。
  3. 再扫内部区域：matrix[i][0] == 0 或 matrix[0][j] == 0 时，把 matrix[i][j] 清零。
  4. 最后按两个布尔，把第 0 行 / 第 0 列整体清零（若需要）。

以示例 [[3,1,2,4],[5,0,7,8],[1,1,1,1],[9,3,1,6]]（0 在 (1,1)）走一遍：

阶段矩阵快照说明
标记前[[3,1,2,4],[5,0,7,8],[1,1,1,1],[9,3,1,6]]第 0 行 / 列本身无 0，两布尔都是 false
第 2 步后[[3,0,2,4],[0,0,7,8],[1,1,1,1],[9,3,1,6]]matrix[0][1]、matrix[1][0] 被置 0，代表“第 1 行、第 1 列要清”
第 3 步后[[3,0,2,4],[0,0,0,0],[1,0,1,1],[9,0,1,6]]内部按标记清完，第 0 行 / 列不受影响，结果正确

下图把上面 4 个步骤串成流程，并逐步演示：

73. 矩阵置零（中等） 解法步骤流程图
图① 解法步骤流程图（共 4 步）。
73. 矩阵置零（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 void setZeroes(vector<vector<int>>& matrix) {
 int m = matrix.size(), n = matrix[0].size();
 bool firstRowZero = false, firstColZero = false;  // 先单独记下第 0 行 / 第 0 列本身有没有 0
 for (int j = 0; j < n; ++j) {
 if (matrix[0][j] == 0) firstRowZero = true;
 }
 for (int i = 0; i < m;
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。