Set Matrix Zeroes 162

Question

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

Example

Given a matrix

[ [1,2], [0,3] ],

return

[ [0,2], [0,0] ]

Challenge

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?

Solution

最蠢的方法是记录所有元素的状态，看是原来是0还是被变成的0，这样需要空间O(mn)。

然后可以用一个数组来记录要变成0的行和列的位置，这样最多有m行n列，需要空间O(m + 1)。

这道题的要求是服用空间，即用matrix的第一行和第一列来存储要变成0的标志的位置。

1. 先确定第一行和第一列是否需要清零

2. 扫描剩下的矩阵元素，如果遇到了0，就将对应的第一行和第一列上的元素赋值为0

3. 根据第一行和第一列的信息，已经可以讲剩下的矩阵元素赋值为结果所需的值了

4. 根据1中确定的状态，处理第一行和第一列

代码如下：

public class Solution {
    /**
     * @param matrix: A list of lists of integers
     * @return: Void
     */
    public void setZeroes(int[][] matrix) {
        // write your code here
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return;
        }

        //确定第一行是否要变成0
        boolean rowZero = false;
        for(int j = 0; j < matrix[0].length; j++){
            if(matrix[0][j] == 0){
                rowZero = true;
                break;
            }
        }
        //确定第一列是否要变成0
        boolean columnZero = false;
        for(int i = 0; i < matrix.length; i++){
            if(matrix[i][0] == 0){
                columnZero = true;
                break;
            }
        }
        //扫描剩下元素，若遇到0，则将其所在行和列的第一个元素变为0
        for(int i = 1; i < matrix.length; i++){
            for(int j = 1; j < matrix[0].length; j++){
                if(matrix[i][j] == 0){
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        //根据第一列信息，将所有要变0的行都变为0
        for(int i = 1; i < matrix.length; i++){
            if(matrix[i][0] == 0){
                for(int j = 1; j < matrix[0].length; j++){
                    matrix[i][j] = 0;
                }
            }
        }
        //根据第一行信息，将所有要变0的列都变为0
        for(int j = 1; j < matrix[0].length; j++){
            if(matrix[0][j] == 0){
                for(int i = 1; i < matrix.length; i++){
                    matrix[i][j] = 0;
                }
            }
        }
        //根据一开始的信息，将第一列变为0
        if(columnZero){
            for(int i = 0; i < matrix.length; i++){
                matrix[i][0] = 0;
            }
        }
        //根据一开始的信息，将第一行变为0
        if(rowZero){
            for(int j = 0; j < matrix[0].length; j++){
                matrix[0][j] = 0;
            }
        }
    }
}