Given an mn matrix, set the entire row and column to 0 for every element that is 0.
The simplest approach is to use an mn matrix to record positions, then set accordingly.
An even simpler approach: use an m+n array to record which rows and columns need to be zeroed.
An even simpler constant-space approach — I thought of one, but it has some issues. Still working on it. For now, here’s the m+n solution.
AC on the first try.
Here is the 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class Solution {
public:
void setRZeros(vector<vector<int> > &matrix,int x)
{
int m = matrix.size();
int n = matrix[0].size();
for(int i = 0;i < n;i++)
{
matrix[x][i] = 0;
}
}
void setCZeros(vector<vector<int> > &matrix,int y)
{
int m = matrix.size();
int n = matrix[0].size();
for(int i = 0;i < m;i++)
{
matrix[i][y] = 0;
}
}
void setZeroes(vector<vector<int> > &matrix) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int m = matrix.size();
int n = matrix[0].size();
int *R = new int[m];
int *C = new int[n];
memset(R,0,m*sizeof(int));
memset(C,0,n*sizeof(int));
for(int i = 0;i < m;i++)
{
for(int j = 0;j < n;j++)
{
if(matrix[i][j] == 0)
{
R[i] = 1;
C[j] = 1;
}
}
}
for(int i = 0;i < m;i++)
{
if(R[i])
setRZeros(matrix,i);
}
for(int i = 0;i < n;i++)
{
if(C[i])
setCZeros(matrix,i);
}
}
};
|