Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

CC150-1.7.java

/**
 * 1.7 Write an algorithm such that if 
 * an element in an MxN matrix is 0, its
 * entire row and column are set to 0.
 * 
 * @Runtime & spaces
 * runtime: O(mn)
 * space: O(1)
*/
//Solution: idea got from zhenzhenanan
//1. 设两个bool变量，一个用来描述第一行是否有零；另一个用来描述第一列是否有零。
//2. 遍历整个matrix，如果某一个元素是0，则把它所在的行的第一个元素设为0，并把它所在的列的第一个元素设为0。
//3. 根据第一行和第一列里面的0，把对应的行和列都设为0。
//4. 根据第一步中的两个变量，把第一行和第一列设为0。
public void setZeros(int[][] matrix) {
	int m = matrix.length;
	int n = matrix[0].length;
	boolean firstRow = false;
	boolean firstCol = false;
	for (int i = 0; i < n; i++) {
		if (matrix[0][i] == 0) {
			firstRow = true;
			break;
		}
	}
	for (int i = 0; i < m; i++) {
		if (matrix[i][0] == 0) {
			firstCol = true;
			break;
		}
	}
	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++){
		if(matrix[i][0]==0){
			for(int j=1;j<n;j++){
				matrix[i][j]=0;
			}
		}
	}
	for(int j=1;j<n;j++){
		if(matrix[0][j]==0){
			for(int i=1;i<m;i++){
				matrix[i][j]=0;
			}
		}
	}
	if(firstRow){
		for(int j=0;j<n;j++)
			matrix[0][j]=0;
	}
	if(firstCol){
		for(int i=0;i<m;i++)
			matrix[i][0]=0;
	}
}