Set Matrix Zeroes leetcode

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

"这是一个矩阵操作的题目，目标很明确，就是如果矩阵如果有元素为0，就把对应的行和列上面的元素都置为0。这里最大的问题就是我们遇到0的时候不能直接把矩阵的行列在当前矩阵直接置0，否则后面还没访问到的会被当成原来是0，最后会把很多不该置0的行列都置0了。
一个直接的想法是备份一个矩阵，然后在备份矩阵上判断，在原矩阵上置0，这样当然是可以的，不过空间复杂度是O(m*n)，不是很理想。
上面的方法如何优化呢？我们看到其实判断某一项是不是0只要看它对应的行或者列应不应该置0就可以，所以我们可以维护一个行和列的布尔数组，然后扫描一遍矩阵记录那一行或者列是不是应该置0即可，后面赋值是一个常量时间的判断。这种方法的空间复杂度是O(m+n)。
其实还可以再优化，我们考虑使用第一行和第一列来记录上面所说的行和列的置0情况，这里问题是那么第一行和第一列自己怎么办？想要记录它们自己是否要置0，只需要两个变量（一个是第一行，一个是第一列）就可以了。然后就是第一行和第一列，如果要置0，就把它的值赋成0（反正它最终也该是0，无论第一行或者第一列有没有0），否则保留原值。然后根据第一行和第一列的记录对其他元素进行置0。最后再根据前面的两个标记来确定是不是要把第一行和第一列置0就可以了。这样的做法只需要两个额外变量，所以空间复杂度是O(1)。
时间上来说上面三种方法都是一样的，需要进行两次扫描，一次确定行列置0情况，一次对矩阵进行实际的置0操作，所以总的时间复杂度是O(m*n)。代码如下："

讲解转自:http://codeganker.blogspot.com/2014/04/set-matrix-zeroes-leetcode.html

//空间O(m + n 做法)
public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int row = matrix.length;
        int column = matrix[0].length;
        boolean[] rowflag = new boolean[row];
        boolean[] colflag = new boolean[column];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (matrix[i][j] == 0) {
                    rowflag[i] = true;
                    colflag[j] = true;
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (rowflag[i] == true) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 0; j < column; j++) {
            for (int i = 0; i < row ; i++) {
                if (colflag[j] == true) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
//空间O(1)做法
public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0|| matrix[0].length == 0) {
            return;
        }
        boolean colflag = false;//记录第一列是否会变成0
        boolean rowflag = false;//记录第一行是否会变成0
        for (int i = 0; i < matrix[0].length; i++) {//判断第一列
            if(matrix[0][i] == 0) {
                rowflag = true;
                break;
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                colflag = true;
                break;
            }
        }
        for (int i = 1; i < matrix.length; i++) {//用第一行和第一列存储0
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < matrix.length; i++) {// 把有0的对应行列都变为0
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowflag) {//判断第一行是否全变成0
            for (int i = 0; i < matrix[0].length; i++) {
                matrix[0][i] = 0;
            }
        }
        if (colflag) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
        return;
    }
}