跳转至

73 矩阵置零

暴力解法

定义行数组row和列数组col表示行/列有元素0

遍历一遍矩阵,找到元素0时,更新行数组row和列数组col为true

判断row[i] || col[j]时,令矩阵为0

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<bool> row(n, false), col(m, false);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(!matrix[i][j]){
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(row[i] || col[j])
                    matrix[i][j] = 0;
            }
        }
    }
};

优化1

我们可以使用矩阵的第一行和第一列代替行数组row和列数组col

但是这种代替方法会导致第一行和第一列原有的值丢失,因此我们需要保存第一行和第一列原有的值

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        // 保存第一行和第一列是否含有元素0的状态
        bool firstRow = false, firstCol = false;
        for(int i = 0; i < n; i++){
            if(!matrix[i][0])
                firstCol = true;
        }
        for(int j = 0; j < m; j++){
            if(!matrix[0][j])
                firstRow = true;
        }
        // 检测除了第一行和第一列外其他部分是否出现元素0
        // matrix[i][0]保存第i行是否要置为0
        // matrix[0][j]保存第j列是否要置为0
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                if(!matrix[i][j]){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // 将矩阵对应行/列置为0(不包括第一行和第一列)
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                if(!matrix[i][0] || !matrix[0][j])
                    matrix[i][j] = 0;
            }
        }
        // 第一行和第一列额外处理
        if(firstRow){
            for(int j = 0; j < m; j++)
                matrix[0][j] = 0;
        }
        if(firstCol){
            for(int i = 0; i < n; i++)
                matrix[i][0] = 0;
        }
    }
};

优化2

优化1使用了两个标记变量firstRow和firstCol,我们还可以优化为一个标记变量

但是我觉得不是特别必要这样优化

思路见

https://leetcode.cn/problems/set-matrix-zeroes/solutions/669901/ju-zhen-zhi-ling-by-leetcode-solution-9ll7/?envType=study-plan-v2&envId=top-100-liked