73. Set Matrix Zeroes

題目有說明到, 希望可以不要用到太多空間

自然最土法煉鋼的方法就先不再多敘述了

我們直接考慮 空間複雜度為O(m+n), 的方法

首先我們有一個長度為m的向量, 紀錄著有0的row, 長度為n的向量紀錄有0的colume,

最後在做inplace的更新

code如下

class Solution {
public:
    void setRowZeros(vector<vector<int>>& matrix, int row){
        for(int i = 0;i < matrix[row].size(); i++){
            matrix[row][i] = 0;
        }
    };
    void setColZeros(vector<vector<int>>& matrix, int col){
        for(int i = 0;i < matrix.size(); i++){
            matrix[i][col] = 0;
        }
    };
    void setZeroes(vector<vector<int>>& matrix) {
        vector<int> record_row;
        vector<int> record_col;
        for(int i=0;i < matrix.size();i++){
            for(int j=0;j < matrix[i].size();j++){
                if(matrix[i][j] == 0){
                    record_row.push_back(i);
                    record_col.push_back(j);
                }
            }
        }
        for(int &i: record_row){
            for(int &j:record_col){
                setRowZeros(matrix, i);
                setColZeros(matrix, j);
            }
        }
    }
};

那題目有給到一個空間複雜度為O(1)的提示, 到底要怎麼做呢?

蠻有趣的, 我們先記錄第一行跟第一列的狀況, 給一個值rowZero, 跟colZero並都設為false, 假設在第一行(列)中有0, 則設為true

第二步我們看其他行列的狀況, 若有0的值, 我們會更新到對應的第一行, 第一列, 更新這兩者的數據, 注意, 我們只看其他行列的狀況, index從1開始

第三部根據第二步所得到的數據, 我們把所有對應到的行列值, 看第一行(列)是否為零 , 同步更新到整張表,注意, 我們只看其他行列的狀況, index從1開始

第四部, 倘若, 第一步就記錄好的第一行(列)就已經存在0, 則我們在這邊統一更新

簡單來說, 我們先用第一行(列)當作紀錄, 用來記錄所有行列的情況, 但我們需要加入第一步跟第四部來確保第一(行)列的情況

這樣著實可以做到空間複雜度O(1)

class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix[0].empty())
            return;
        int m = matrix.size();
        int n = matrix[0].size();
        bool rowZero = false;
        bool colZero = false;
        // step 1
for(int i = 0;i < m; i++){
           if(matrix[i][0] == 0){
               rowZero = true;
           }
        }
        for(int j = 0;j < n; j++){
            if(matrix[0][j] == 0){
                colZero = true;
            }
        }
          // step 2
        for(int i = 1;i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == 0){
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
          // step 3
        for(int i = 1; i < m; i++){
            for(int j =1; j <n;j++){
                if(matrix[0][j]==0 || matrix[i][0]==0){
                    matrix[i][j]=0;
                }
            }
        }
          // step 4
        if(rowZero){
            for(int i = 0; i < m; ++i){
                matrix[i][0] = 0;
            }
        }
        if(colZero){
            for(int i = 0; i <n; i++){
                matrix[0][i] = 0;
            }
        }
    }
};