题目

思路

一句话：把“哪些行、哪些列要清零”记下来，再统一清零；最高明的记法，是把标记写进矩阵自己的第 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)）走一遍：

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

C++

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;
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。