LeetCode 73. Set Matrix Zeroes [Medium] [C++] 解題筆記

這題給定一個 m x n 大小的陣列，如果任一行或列中有一個元素為 0 則整行或整列皆需改為 0。

另外題目特別要求必須要在 O(1) 空間複雜度下完成 (in-place)。

EX:

    Input: 
    [
      [1,1,1],
      [1,0,1],
      [1,1,1]
    ]
    Output: 
    [
      [1,0,1],
      [0,0,0],
      [1,0,1]
    ]

想法:

    因為要考慮空間複雜度，所以不能額外宣告一個二維陣列來紀錄各元素的值(O(m*n) space)，

宣告兩個一維陣列來分別紀錄每一行/列有無出現 0 (O(m + n) space)也不可行，

因此這邊利用第一行與第一列來紀錄各行各列有無出現 0，也因為用第一行與第一列來紀錄，

所以我們必須先額外檢查第一行與第一列是否有出現 0，若有則在最後將整行/列變成 0。

Complexity: O(m*n) time, O(1) space.

完整程式碼:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) { return; }
        int row = matrix.size();
        int col = matrix[0].size();
        bool first_row_zero = false;
        bool first_col_zero = false;
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                first_col_zero = true;
                break;
            }
        }
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                first_row_zero = true;
                break;
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        if (first_row_zero) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
        if (first_col_zero) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
        
        return;
    }
};