题目链接 · 灵神原题解（署名来源）

本文从 $\mathcal{O}(m+n)$ 额外空间的思路开始，然后优化到 $\mathcal{O}(1)$ 空间。

规则

对于 $\mathit{\text{matrix}}[i][j]$，如果 $i$ 行有 $0$，或者 $j$ 列有 $0$，那么把 $\mathit{\text{matrix}}[i][j]$ 变成 $0$，否则 $\mathit{\text{matrix}}[i][j]$ 不变（仍然为 $1$）。

方法一：使用额外数组

用一个长为 $m$ 的布尔数组 $\mathit{\text{rowHasZero}}$ 记录每一行是否包含 $0$。

• 遍历 $\mathit{\text{matrix}}[i]$，如果包含 $0$，那么置 $\mathit{\text{rowHasZero}}[i]=\mathtt{\text{true}}$。

用一个长为 $n$ 的布尔数组 $\mathit{\text{colHasZero}}$ 记录每一列是否包含 $0$。

• 遍历 $\mathit{\text{matrix}}$ 的 $j$ 列，如果包含 $0$，那么置 $\mathit{\text{colHasZero}}[j]=\mathtt{\text{true}}$。

然后，再次遍历 $\mathit{\text{matrix}}$。对于 $\mathit{\text{matrix}}[i][j]$，如果 $\mathit{\text{rowHasZero}}[i]=\mathtt{\text{true}}$ 或者 $\mathit{\text{colHasZero}}[j]=\mathtt{\text{true}}$，说明 $i$ 行有 $0$，或者 $j$ 列有 $0$，把 $\mathit{\text{matrix}}[i][j]$ 变成 $0$。

答疑

问：能不能在发现 $\mathit{\text{matrix}}[i][j]=0$ 时，直接把 $i$ 行 $j$ 列全变成 $0$？

答：这样做是错误的。如示例 1，如果直接全变成 $0$，那么继续遍历，发现 $\mathit{\text{matrix}}[1][2]=0$，我们会误以为 $\mathit{\text{matrix}}[1][2]$ 一开始就是 $0$，然后把 $2$ 列（最右边那一列）全变成 $0$。

Python 解法1

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        row_has_zero = [0 in row for row in matrix]  # 行是否包含 0
        col_has_zero = [0 in col for col in zip(*matrix)]  # 列是否包含 0

        for i, row0 in enumerate(row_has_zero):
            for j, col0 in enumerate(col_has_zero):
                if row0 or col0:  # i 行或 j 列有 0
                    matrix[i][j] = 0  # 题目要求原地修改，无返回值

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int8_t> row_has_zero(m); // 行是否包含 0
        vector<int8_t> col_has_zero(n); // 列是否包含 0

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row_has_zero[i] = col_has_zero[j] = true;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row_has_zero[i] || col_has_zero[j]) { // i 行或 j 列有 0
                    matrix[i][j] = 0; // 题目要求原地修改，无返回值
                }
            }
        }
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\mathit{\text{matrix}}$ 的行数和列数。
• 空间复杂度：$\mathcal{O}(m+n)$。

方法二：不使用额外数组

回想一下 Excel 表格，通常用第一行和第一列保存汇总信息。

对于本题，能否把数据保存到 $\mathit{\text{matrix}}$ 的第一行和第一列中呢？

用第一列的 $\mathit{\text{matrix}}[i][0]$ 代替 $\mathit{\text{rowHasZero}}[i]$：如果 $i$ 行有 $0$，那么置 $\mathit{\text{matrix}}[i][0]=0$。

用第一行的 $\mathit{\text{matrix}}[0][j]$ 代替 $\mathit{\text{colHasZero}}[j]$：如果 $j$ 列有 $0$，那么置 $\mathit{\text{matrix}}[0][j]=0$。

然后，再次遍历 $\mathit{\text{matrix}}$。对于 $\mathit{\text{matrix}}[i][j]$，如果 $\mathit{\text{matrix}}[i][0]=0$ 或者 $\mathit{\text{matrix}}[0][j]=0$，说明 $i$ 行有 $0$ 或者 $j$ 列有 $0$，把 $\mathit{\text{matrix}}[i][j]$ 变成 $0$。

看上去，问题解决了？

然而，如果第一行全为 $1$，第一列包含 $0$（或者反过来），我们会置 $\mathit{\text{matrix}}[0][0]=0$。修改后，根据定义，我们会误认为第一行和第一列都包含 $0$，最终会把第一行和第一列都变成 $0$。如何修复这个 bug？

解决办法：在一开始，额外用两个布尔变量分别记录第一行是否包含 $0$，第一列是否包含 $0$。最后，如果第一行在一开始就包含 $0$，那么把第一行全变成 $0$；如果第一列在一开始就包含 $0$，那么把第一列全变成 $0$。

既然最后会单独修改第一行和第一列，那么在修改 $\mathit{\text{matrix}}[i][j]$ 时，可以先跳过第一行和第一列，最后再修改。

写法一

Python 解法3

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        first_row_has_zero = 0 in matrix[0]  # 记录第一行是否包含 0
        first_col_has_zero = any(row[0] == 0 for row in matrix)  # 记录第一列是否包含 0

        # 用第一列 matrix[i][0] 保存 row_has_zero[i]
        # 用第一行 matrix[0][j] 保存 col_has_zero[j]
        for i in range(1, m):  # 无需遍历第一行，如果 matrix[0][j] 本身是 0，那么相当于 col_has_zero[j] 已经是 True
            for j in range(1, n):  # 无需遍历第一列，如果 matrix[i][0] 本身是 0，那么相当于 row_has_zero[i] 已经是 True
                if matrix[i][j] == 0:
                    matrix[i][0] = 0  # 相当于 row_has_zero[i] = True
                    matrix[0][j] = 0  # 相当于 col_has_zero[j] = True

        for i in range(1, m):  # 跳过第一行，留到最后修改
            for j in range(1, n):  # 跳过第一列，留到最后修改
                if matrix[i][0] == 0 or matrix[0][j] == 0:  # i 行或 j 列有 0
                    matrix[i][j] = 0

        # 如果第一列一开始就包含 0，那么把第一列全变成 0
        if first_col_has_zero:
            for row in matrix:
                row[0] = 0

        # 如果第一行一开始就包含 0，那么把第一行全变成 0
        if first_row_has_zero:
            for j in range(n):
                matrix[0][j] = 0

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool first_row_has_zero = ranges::contains(matrix[0], 0); // 记录第一行是否包含 0
        bool first_col_has_zero = ranges::any_of(matrix, [](auto& row) { return row[0] == 0; }); // 记录第一列是否包含 0

        // 用第一列 matrix[i][0] 保存 row_has_zero[i]
        // 用第一行 matrix[0][j] 保存 col_has_zero[j]
        for (int i = 1; i < m; i++) { // 无需遍历第一行，如果 matrix[0][j] 本身是 0，那么相当于 col_has_zero[j] 已经是 true
            for (int j = 1; j < n; j++) { // 无需遍历第一列，如果 matrix[i][0] 本身是 0，那么相当于 row_has_zero[i] 已经是 true
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0; // 相当于 row_has_zero[i] = true
                    matrix[0][j] = 0; // 相当于 col_has_zero[j] = true
                }
            }
        }

        for (int i = 1; i < m; i++) { // 跳过第一行，留到最后修改
            for (int j = 1; j < n; j++) { // 跳过第一列，留到最后修改
                if (matrix[i][0] == 0 || matrix[0][j] == 0) { // i 行或 j 列有 0
                    matrix[i][j] = 0;
                }
            }
        }

        // 如果第一列一开始就包含 0，那么把第一列全变成 0
        if (first_col_has_zero) {
            for (auto& row : matrix) {
                row[0] = 0;
            }
        }

        // 如果第一行一开始就包含 0，那么把第一行全变成 0
        if (first_row_has_zero) {
            ranges::fill(matrix[0], 0);
        }
    }
};

写法二

记录行列是否包含 $0$ 时，上面的代码没有遍历第一列。如果顺带遍历第一列呢？

• 如果第一列全为 $1$，那么在遍历过程中，不会修改 $\mathit{\text{matrix}}[0][0]$，所以遍历结束后 $\mathit{\text{matrix}}[0][0]$ 仍然是 $1$。
• 如果第一列包含 $0$，那么在遍历过程中，我们会把 $\mathit{\text{matrix}}[0][0]$ 置为 $0$。

所以可以直接用 $\mathit{\text{matrix}}[0][0]$ 表示「第一列是否在一开始包含 $0$」。

Python 解法5

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        first_row_has_zero = 0 in matrix[0]

        for i in range(1, m):
            for j in range(n):  # 如果第一列包含 0，那么 matrix[0][0] 会置为 0
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0

        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        # 注意顺序，先改第一列，再改第一行（避免把 matrix[0][0] 从 1 改成 0 影响判断）
        if matrix[0][0] == 0:  # 替换原来的 first_col_has_zero
            for row in matrix:
                row[0] = 0

        if first_row_has_zero:
            for j in range(n):
                matrix[0][j] = 0

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool first_row_has_zero = ranges::contains(matrix[0], 0);

        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) { // 如果第一列包含 0，那么 matrix[0][0] 会置为 0
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 注意顺序，先改第一列，再改第一行（避免把 matrix[0][0] 从 1 改成 0 影响判断）
        if (matrix[0][0] == 0) { // 替换原来的 first_col_has_zero
            for (auto& row : matrix) {
                row[0] = 0;
            }
        }

        if (first_row_has_zero) {
            ranges::fill(matrix[0], 0);
        }
    }
};

写法三

把 $\mathit{\text{matrix}}[i][j]$ 置 $0$ 的循环，可以倒着遍历 $i$ 行，这样可以直接修改第一列。

对比一下，如果正着遍历 $i$ 行，如果提前把 $\mathit{\text{matrix}}[i][0]$ 改成 $0$，会误认为这一行要全部变成 $0$。

下面的代码，前两个循环可以合在一起看，我们遍历了一次 $\mathit{\text{matrix}}$；后两个循环可以合在一起看，我们又遍历了一次 $\mathit{\text{matrix}}$。

Python 解法7

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        first_row_has_zero = 0 in matrix[0]

        for i in range(1, m):
            for j in range(n):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0

        for i in range(1, m):
            # 倒着遍历，避免提前把 matrix[i][0] 改成 0，误认为这一行要全部变成 0
            for j in range(n - 1, -1, -1):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        if first_row_has_zero:
            for j in range(n):
                matrix[0][j] = 0

C++ 解法7

// C++ 版待补充

C++ 解法8

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool first_row_has_zero = ranges::contains(matrix[0], 0);

        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        for (int i = 1; i < m; i++) {
            // 倒着遍历，避免提前把 matrix[i][0] 改成 0，误认为这一行要全部变成 0
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        if (first_row_has_zero) {
            ranges::fill(matrix[0], 0);
        }
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别是 $\mathit{\text{matrix}}$ 的行数和列数。
• 空间复杂度：$\mathcal{O}(1)$。

相似题目

1582. 二进制矩阵中的特殊位置

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府