73. 矩阵置零

原题链接

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

• \(m\) \(=\) \(matrix.length\)
• \(n\) \(=\) \(matrix[0].length\)
• \(1\) \(≤\) \(m, n\) \(≤\) \(200\)
• \(-2^{31}\) \(≤\) \(matrix[i][j]\) \(≤\) \(2^{31} - 1\)

进阶：

• 一个直观的解决方案是使用  \(O(mn)\) 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 \(O(m + n)\) 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个仅使用常量空间的解决方案吗？

---

思路

原地算法 \(O(nm)\)

我们可以使用两个标记变量 row0 , col0 分别记录第一行和第一列是否包含0。

1. 预处理出两个变量记录第一行和第一列是否有0。
2. 遍历整个矩阵，用矩阵的第一行和第一列记录对应的行和列是否有0。
3. 把含有0的行和列都置成0。

复杂度分析

时间复杂度：\(O(mn)\)，其中 \(m\) 是矩阵的行数，\(n\) 是矩阵的列数。我们至多只需要遍历该矩阵两次。

空间复杂度：\(O(1)\)。我们只需要常数空间存储若干变量。

---

代码

C++

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

        // find row-0
        for (int i = 0; i < m; i++)
            if (!matrix[0][i])
                row0 = true;

        // find col-0
        for (int i = 0; i < n; i++)
            if (!matrix[i][0])
                col0 = true;

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

        // col -> 0
        for (int i = 1; i < m; i++)
            if (!matrix[0][i])
                for (int j = 1; j < n; j++)
                    matrix[j][i] = 0;

        // row -> 0
        for (int i = 1; i < n; i++)
            if (!matrix[i][0])
                for (int j = 1; j < m; j++)
                    matrix[i][j] = 0;

        // if row-0 has zero, transform all of row-0 to zero
        if (row0)
            for (int i = 0; i < m; i++)
                matrix[0][i] = 0;

        // if col-0 has zero, transform all of col-0 to zero
        if (col0)
            for (int i = 0; i < n; i++)
                matrix[i][0] = 0;
    }
};