我好菜
space compelexity O(m + n)
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
| class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
unordered_set<int> row;
unordered_set<int> col;
for(int i = 0; i < matrix.size(); ++i)
{
for(int j = 0; j < matrix[0].size(); ++j)
{
if(matrix[i][j] == 0)
{
row.insert(i);
col.insert(j);
}
}
}
for(int i = 0; i < matrix.size(); ++i)
{
for(int j = 0; j < matrix[0].size(); ++j)
{
if(row.find(i) != row.end() || col.find(j) != col.end())
matrix[i][j] = 0;
}
}
}
};
|
space compelexity O1)
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
| class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool firstColZero = false;
for(int i = 0; i < m; ++i)
{
if(matrix[i][0] == 0)
firstColZero = 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 = 1; i < n; ++i)
matrix[0][i] = 0;
if(firstColZero)
for(int i = 0; i < m; ++i)
matrix[i][0] = 0;
}
};
|
因为第一行和第一列为0都由一个matrix[0][0]指定，将导致二者无法区分，所以用matrix[0][0]指定第一行，isCol这个额外的变量指定第一列。
注意要先填充第一行第一列以外的内容再去填充第一行第一列，不然后面数据会被填充的0所干扰