Solution 1: if matrix[i][j] is 0, mark matrix[i][0] and matrix[0][j] to 0. Then go through entire matrix again, set related matrix[i][j]=0 if either matrix[i][0] or matrix[0][j] is marked.
public class Solution {
public void setZeroes(int[][] matrix) {
int m=matrix.length;
if (m==0) return;
int n=matrix[0].length;
boolean row0=false, col0=false;
for (int j=0; j<n; j++) if (matrix[0][j]==0) row0=true;
for (int i=0; i<m; i++) if (matrix[i][0]==0) col0=true;
for (int i=1; i<m; i++) {
for (int j=1; j<n; j++) {
if (matrix[i][j]==0) {
matrix[0][j]=0;
matrix[i][0]=0;
}
}
}
for (int i=1; i<m; i++)
for (int j=1; j<n; j++)
if (matrix[0][j]==0 || matrix[i][0]==0) matrix[i][j]=0;
if (row0) for (int j=0; j<n; j++) matrix[0][j]=0;
if (col0) for (int i=0; i<m; i++) matrix[i][0]=0;
}
}
没有评论:
发表评论