Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Answer:
Space:O(1)
public void setZeroes(int[][] matrix) {
if(matrix == null)return;
int m = matrix.length;
if(m == 0)return;
if(matrix[0] == null)return;
int n = matrix[0].length;
if(n==0)return;
boolean left = false;
boolean top = false;
for (int i=0;i<m;i++){
if (matrix[i][0]==0){
left = true;
}
}
for (int i=0;i<n;i++){
if (matrix[0][i]==0){
top = true;
}
}
for(int i=1;i<m;++i){
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(left){
for(int i=0;i<m;++i){
matrix[i][0] = 0;
}
}
if(top){
for(int i=0;i<n;++i){
matrix[0][i] = 0;
}
}
return;
}
No comments:
Post a Comment