|
| 1 | +packageAlgorithms.array; |
| 2 | + |
| 3 | +publicclassSetZeroes { |
| 4 | +publicstaticvoidmain(String[]strs) { |
| 5 | +int[][]matrix = { |
| 6 | + {0,0,0,5},{4,3,1,4},{0,1,1,4},{1,2,1,3},{0,0,1,1} |
| 7 | + }; |
| 8 | + |
| 9 | +setZeroes(matrix); |
| 10 | + } |
| 11 | + |
| 12 | +publicstaticvoidsetZeroes(int[][]matrix) { |
| 13 | +if (matrix ==null ||matrix.length ==0 |
| 14 | + ||matrix[0].length ==0) { |
| 15 | +return; |
| 16 | + } |
| 17 | + |
| 18 | +booleanrow1Zero =false; |
| 19 | +booleancol1Zero =false; |
| 20 | + |
| 21 | +introws =matrix.length; |
| 22 | +intcols =matrix[0].length; |
| 23 | + |
| 24 | +// Determine if the first column should be Zero. |
| 25 | +for (inti =0;i <rows;i++) { |
| 26 | +if (matrix[i][0] ==0) { |
| 27 | +col1Zero =true; |
| 28 | +break; |
| 29 | + } |
| 30 | + } |
| 31 | + |
| 32 | +// Determine if the first row should be Zero. |
| 33 | +for (inti =0;i <cols;i++) { |
| 34 | +if (matrix[0][i] ==0) { |
| 35 | +row1Zero =true; |
| 36 | +break; |
| 37 | + } |
| 38 | + } |
| 39 | + |
| 40 | +// we use the first row and the first col as the flag to record the |
| 41 | +// cells whether or not set to 0. |
| 42 | +for (inti =1;i <rows;i++) { |
| 43 | +for (intj =1;j <cols;j++) { |
| 44 | +// 注意了，这个矩阵是0和非0，并不是0和1. |
| 45 | +if (matrix[i][j] ==0) { |
| 46 | +// set the flag in the first line and the first column |
| 47 | +matrix[i][0] =0; |
| 48 | +matrix[0][j] =0; |
| 49 | + } |
| 50 | + } |
| 51 | + } |
| 52 | + |
| 53 | +// set the inner cells. |
| 54 | +// Be careful: i, j start from 1. |
| 55 | +for (inti =1;i <rows;i++) { |
| 56 | +for (intj =1;j <cols;j++) { |
| 57 | +if (matrix[i][0] ==0 |
| 58 | + ||matrix[0][j] ==0) { |
| 59 | +matrix[i][j] =0; |
| 60 | + } |
| 61 | + } |
| 62 | + } |
| 63 | + |
| 64 | +// set the first row. |
| 65 | +if (row1Zero) { |
| 66 | +for (inti =0;i <cols;i++) { |
| 67 | +matrix[0][i] =0; |
| 68 | + } |
| 69 | + } |
| 70 | + |
| 71 | +// set the first col. |
| 72 | +if (col1Zero) { |
| 73 | +for (inti =0;i <rows;i++) { |
| 74 | +matrix[i][0] =0; |
| 75 | + } |
| 76 | + } |
| 77 | + |
| 78 | +return; |
| 79 | + } |
| 80 | +} |