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.
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;
}
}
}
解法三性能：