cc150-1.7

gistfile1.java

/*
 * Write an algorithm such that if an element in an MxN matrix is 0, its entire row and
column are set to 0
algorithm
  we only need know  which row and  column to be set to  0 
  so  we need  set two boolean array to  mark the    rows and columns should be set to  0
  O(mn) and space O(n+m)
  */
	public static void main(String[] args) {
		int[][] data= new int[][]{
				  { 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
				  { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
				  { 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },
				  { 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 },
				  { 0, 0, 0, 0, 0, 1, 0, 0, 1, 0 }
				};
       resetMatix(data);
	}

	private static void resetMatix(int[][] data) {
		boolean[] row = new boolean[data.length];
		boolean[] col = new boolean[data[0].length];
		for(int i=0; i <data.length; i++)
		{
			for(int j=0;j<data[0].length;j++){
				if(data[i][j]==0){
					row[i]=true;
					col[j]=true;
				}
			}
		}
		for(int i=0; i <data.length; i++)
		{
			for(int j=0;j<data[0].length;j++){
				if(row[i]||col[j]){
					data[i][j] = 0 ;
				}
			}
		}
		  
	}

}