解题思路

这个题目想要通过并不难，主要是题目分别有三个空间复杂度的要求：$O(MN)$，$O(M+N)$，$O(1)$。

首先介绍一下什么是原地算法：即在函数的输入矩阵上直接修改，而不是 return 一个矩阵。所以，力扣判定程序正确性的时候，仍然根据同一个 matrix 变量来判定。力扣判定的代码类似于：

matrix = [输入矩阵]
setZeroes(matrix)
assert matrix 与预期矩阵相等

本题难点：如果在输入矩阵上原地修改把行列修改成了 0，那么再遍历到 0 的时候就不知道是原本数组中的 0 还是我们修改得到的 0。所有的解法都是为了解决该问题。

一、空间复杂度 $O(MN)$ 的算法

$O(MN)$ 的算法比较直接了当，有两种思路：

1.1 复制原数组

只要把输入的原始数组复制一份，那么根据 copy 出来的数组判断某个位置是否为 0，就是原始数组中的该位置是0。遇到 matrix_copy 的一个位置是 0，那么直接修改 matrix 的行列全部是 0。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        if not matrix or not matrix[0]:
            return
        M, N = len(matrix), len(matrix[0])
        matrix_copy = copy.deepcopy(matrix)
        for i in range(M):
            for j in range(N):
                if matrix_copy[i][j] == 0:
                    for k in range(M):
                        matrix[k][j] = 0
                    for k in range(N):
                        matrix[i][k] = 0

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return;
        vector<vector<int>> newM(matrix);
        const int M = matrix.size(), N = matrix[0].size();
        for (int r = 0; r < M; ++r) {
            for (int c = 0; c < N; ++c) {
                if (newM[r][c] == 0) {
                    for (int j = 0; j < N; ++j) {
                        matrix[r][j] = 0;
                    }
                    for (int i = 0; i < M; ++i) {
                        matrix[i][c] = 0;
                    }
                }
            }
        }
    }
};

时间复杂度：$O(MN*(M+N))$
空间复杂度：$O(MN)$
1.2 保存数组中 0 出现的位置

上面代码的思路是每次遇到 0 都去修改对应的行列。

这里的思路是对数组先做一次遍历，保存所有 0 出现的下标。最后对于每个 0 出现的位置都去修改一下其所在的行列。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return;
        const int M = matrix.size(), N = matrix[0].size();
        queue<pair<int, int>> q;
        for (int r = 0; r < M; ++r) {
            for (int c = 0; c < N; ++c) {
                if (matrix[r][c] == 0) {
                    q.push({r, c});
                }
            }
        }
        while (!q.empty()) {
            auto p = q.front(); q.pop();
            for (int j = 0; j < N; ++j) {
                matrix[p.first][j] = 0;
            }
            for (int i = 0; i < M; ++i) {
                matrix[i][p.second] = 0;
            }
        }
    }
};

时间复杂度：$O(MN*(M+N))$
空间复杂度：$O(MN)$

二、空间复杂度 $O(M + N)$ 的算法

在空间复杂度是 $O(MN)$ 的解法中，我们需要对于每个出现的 0 都修改对应的行列。那么，如果同一个行（列）中如果出现了两个 0 ，则需要把该行（列）置两遍 0 。无论是空间还是时间复杂度，都不好。

一个容易得到的方法是：遍历一次矩阵，记录一下每行、列是否出现了 0；如果出现了 0，最终将此行列置为 0。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        if not matrix or not matrix[0]:
            return
        M, N = len(matrix), len(matrix[0])
        row, col = set(), set()
        for i in range(M):
            for j in range(N):
                if matrix[i][j] == 0:
                    row.add(i)
                    col.add(j)
        for i in range(M):
            for j in range(N):
                if i in row or j in col:
                    matrix[i][j] = 0

时间复杂度：$O(MN)$
空间复杂度：$O(M+N)$

三、空间复杂度 $O(1)$ 的算法

空间复杂度为 $O(1)$，也就是说只能用常量的空间，难度就突然加大了。

方法的整体思想是：使用第 0 行和第 0 列来保存 matrix[1:M][1:N] 中是否出现了 0；那么第 0 行和第 0 列的数据就不是输入的原始数据了。因此，为了知道第 0 行和第 0 列是否有 0，就必须提前统计。

这个方法可以分为四步走：
1. 统计 matrix 第 0 行和第 0 列是否有 0，保存到 row0, col0 中；
2. 遍历 matrix[1:M][1:N] 看当前位置是否有 0，如果有 0，则把信息记录到 matrix 的第 0 行以及第 0 列中。
3. 根据 matrix 中第 0 行以及第 0 列的 0，将 matrix[1:M][1:N] 对应的行或者列全部置 0；
4. 根据 row0, col0 判断第 0 行和第 0 列是否需要全部置 0。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        if not matrix or not matrix[0]:
            return
        M, N = len(matrix), len(matrix[0])
        row0, col0 = False, False
        for i in range(M):
            if matrix[i][0] == 0:
                col0 = True
        for j in range(N):
            if matrix[0][j] == 0:
                row0 = True
        for i in range(1, M):
            for j in range(1, N):
                if matrix[i][j] == 0:
                    matrix[i][0] = 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
        if row0:
            for j in range(N):
                matrix[0][j] = 0
        if col0:
            for i in range(M):
                matrix[i][0] = 0

时间复杂度：$O(MN)$
空间复杂度：$O(1)$

刷题心得

今天这个题，我个人认为能想到空间复杂度 $O(M+N)$ 的解法已经可以了。在实际工作中，如果写出空间复杂度为 $O(1)$ 的解法，可读性太差，有可能会被同事骂。

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】73. 矩阵置零