LeetCode-73-Set Matrix Zeroes

Matrix Zeroes

 

来自 <https://leetcode.com/problems/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.

click to show follow up.

Follow up:

Did you use extra space?

A straight forward solution using O(mn) space is probably a bad idea.

A simple improvement uses O(m + n) space, but still not the best solution.

Could you devise a constant space solution?

 题目解读

给定一个矩阵，如果矩阵中的某个元素为0，则将其所在的整行和整列全部设置为0，在原来的矩阵中设置。

 

题目解析：

解法一：使用 O(mn)额外空间，创建一个和原来矩阵大小相同的矩阵matrixTemp，根据原来矩阵matrix的元素值设置matrix矩阵中行和列为。最后再将matrixTemp中的元素复制给matrix.

 

解法二：创建两个数组zeroRows和zeroCols，zeroRows记录那些行应该置为0，zeroCols记录那些列应该置为0.先遍历一遍矩阵，给数组zeroRows和zeroCols中的元素赋值。最后根据数组zeroRows和zeroCols中的元素，将矩阵中的某些行和列设置为0。

 

解法三：利用第0行和第0列记录将要置零的行和列，分如下四步

Analysis

This problem should be solved in place, i.e., no other array should be used. We can use the first column and the first row to track if a row/column should be set to 0.

Since we used the first row and first column to mark the zero row/column, the original values are changed.

 

Specifically, given, the following matrix

 this problem can be solved by following 4 steps:

Step 1:

First row contains zero = true;

First column contains zero = false;

Step 2: use first row and column to mark zero row and column.

 

 

Step 3: set each elements by using marks in first row and column.

 Step 4: Set first column and row by using marks in step 1.

 来自 <http://www.programcreek.com/2012/12/leetcode-set-matrix-zeroes-java/>

 

解法一代码：

public class Solution {
    public void setZeroes(int[][] matrix) {
              int[][] matrixTemp = new int[matrix.length][matrix[0].length];
		//将matrix中的元素全部复制给tempMatrix
		for(int i=0; i<matrix.length; i++) {
			for(int j=0; j<matrix[0].length; j++) {
				matrixTemp[i][j] = matrix[i][j];
			}
		}
		
		for(int i=0; i<matrix.length; i++) {
			for(int j=0; j<matrix[0].length; j++) {
				if(0 == matrix[i][j]){
					//将j列元素置零
					for(int m=0; m<matrix.length; m++) {
						matrixTemp[m][j] = 0;
					}
					
					//将i行元素置零
					for(int n=0; n<matrix[0].length; n++) {
						matrixTemp[i][n] = 0;
					}
				}	
			}
		}
		for(int i=0; i<matrix.length; i++) {
			for(int j=0; j<matrix[0].length; j++) {
				matrix[i][j] = matrixTemp[i][j];
			}
		}
    }
}

解法一性能：

 

解法二代码：

public class Solution {
    public void setZeroes(int[][] matrix) {
		//用于记录那些行应该设置为0
        int[] zeroRows = new int[matrix.length];
        for(int i=0; i<matrix.length; i++) {
        	zeroRows[i] = 1;
        }

        //记录那些列应该设置为0
        int[] zeroCols = new int[matrix[0].length];
        for(int i=0; i<matrix[0].length; i++) {
        	zeroCols[i] = 1;
        }
        
        for(int i=0; i< matrix.length; i++) {
        	for(int j=0; j<matrix[0].length; j++) {
        		if(0 == matrix[i][j]){
        			zeroRows[i] = 0;
        			zeroCols[j] = 0;
        		}
        	}
        }
        
       //将行置为0
        for(int i=0; i<matrix.length; i++) {
        	if(0 == zeroRows[i]) {
        		for(int j=0; j<matrix[0].length; j++) {
        			matrix[i][j] = 0;
        		}
        	}
        }
        
        //将列置为0
        for(int i=0; i<matrix[0].length; i++) {
        	if(0 == zeroCols[i]) {
        		for(int j=0; j<matrix.length; j++) {
        			matrix[j][i]=0;
        		}
        	}
        }
    }
}

 解法二性能：

 

解法三代码

public class Solution {
    public void setZeroes(int[][] matrix) {
/**
		 * 记录第一行第一列是否为零
		 */
		boolean firstRowZero = false;
		boolean firstColZero = false;
		
		/**
		 * 判断第一列是否为0
		 */
		for(int i=0; i<matrix.length; i++) {
			if(0 == matrix[i][0]) {
				firstColZero = true;
			}
		}
		
		/**
		 * 判断第一行是否为0
		 */
		for(int i=0; i<matrix[0].length; i++) {
			if(0 == matrix[0][i])
				firstRowZero = true;
		}
		
		/**
		 * 遍历整个矩阵，将要置为0的行和列标注在第0行和第0列
		 */
		for(int i=0; i<matrix.length; i++) {
			for(int j=0; j<matrix[0].length; j++) {
				if(0 == matrix[i][j]){
					matrix[0][j] = 0;
					matrix[i][0] = 0;
				}
			}
		}
		
		for(int i=1; i<matrix.length; i++) {
			for(int j=1; j<matrix[0].length; j++) {
				if((matrix[0][j] == 0) || (matrix[i][0] == 0))
					matrix[i][j] = 0;
			}
		}
		/**
		 * 第一行是否置零
		 */
		if(firstRowZero) {
			for(int i=0; i<matrix[0].length; i++)
				matrix[0][i] = 0;
		}
		
		/**
		 * 第一列是否置零
		 */
		if(firstColZero) {
			for(int i=0; i<matrix.length; i++)
				matrix[i][0] = 0;
		}
    }
}

解法三性能：