runtime 16 ms, beats 90.83% of cpp submissions
O(mn) solution with explanation
tags: none
🔗 link
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; for(int i=0;i<m;i++){ if(matrix[i][0]==0) first_col = true; for(int j=1;j<n;j++){ if(matrix[i][j]==0){ matrix[i][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) { matrix[i][j] = 0; } } } if(matrix[0][0] == 0){ for(int i=0;i<n;i++){ matrix[0][i] = 0; } } if(first_col == true){ for(int i=0;i<m;i++){ matrix[i][0] = 0; } } } };
|