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;
}
}
}
};