runtime 16 ms, beats 90.83% of cpp submissions
O(mn) solution with explanation

tags: none

Set Matrix Zeroes

📖 description

給定一個陣列，要求將所有包含 0 元素所在的行和列寫成 0 

ex.
    Input: 
        matrix = [[1,1,1],[1,0,1],[1,1,1]]

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

🧠 solution

如果單純把行和列的編號儲存起來，並一次改變，這樣做的空間複雜度為 O(m+n) ，而此題實際上是不需要使用額外空間的。

我們可以將每行每列的資料存在陣列內的第一行與第一列，如果剛行/列需要變成 0 ，就標記在上面，而我們只需要再遍歷一次陣列，便可以確定該位置需不需要寫成 0 。

除此之外，我們也必須額外確認第一行或第一列是否需要寫成 0 ，因為我們先前將該區域作為暫存了。

⏳ time complexity

遍歷兩次陣列，時間複雜度 O(mn)
總時間複雜度 O(mn)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool first_col = false;     // 看第一行是否需要轉換成 0 
        for(int i=0;i<m;i++){
            if(matrix[i][0]==0) first_col = true;
            for(int j=1;j<n;j++){   // 從 1 開始，因為第一個 column 需要作為暫存
                if(matrix[i][j]==0){
                    matrix[i][0] = 0;   // 紀錄該行與列需要變成 0 
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {   // 如果該行或該列需要變成 0 
                    matrix[i][j] = 0;
                }
            }
        }
        if(matrix[0][0] == 0){      // 第一列需要變成 0 
            for(int i=0;i<n;i++){
                matrix[0][i] = 0;
            }
        }
        if(first_col == true){      // 第一行需要變成 0 
            for(int i=0;i<m;i++){
                matrix[i][0] = 0;
            }
        }
    }
};