2015年9月27日星期日

Leetcode 73 Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

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;  
   }  
 }  

没有评论:

发表评论