leetcode: 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?

原问题链接：https://leetcode.com/problems/set-matrix-zeroes/

 

问题分析

　　这个问题在之前的一篇文章里有过详细的讨论。 这个问题的主要思路在于，当我们每次在矩阵里碰到一个为0的元素的时候不能直接就将它的当前行和列设置为0。因为一旦这样设置之后，就可能将后面的元素里那些原来不是0的元素设置成了0。而这样在后面的遍历里会以为这些元素是本来为0的，可能导致最后设置的结果不对。所以这里采用的是一种类似于坐标图的办法，将矩阵的第一行和第一列作为标记轴。在从除第一行第一列的元素开始进行遍历的时候，碰到为0的元素就将对应的行和列的坐标对应的值设置为0。这样遍历完元素之后就将对应的点都打好了。剩下的就是遍历第一行和第一列，将碰到为0的元素对应的行或者列全置为0。

　　这里还有一个比较容易错的细节，就是我们后面的遍历会修改第一行和第一列的值。如果第一行或者第一列里原来有0的元素的话，照理说它们是应该要把当前行或者列清零的。所以我们实现要把这两种可能出现的情况给记录下来，然后才做元素遍历。在这些坐标点都设置完之后再来将坐标轴的元素设置好。

　　详细的实现如下：

 

public class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean rowZero = false, colZero = false;
        for(int i = 0; i < m; i++)
            if(matrix[i][0] == 0)
                colZero = true;
        for(int i = 0; i < n; i++)
            if(matrix[0][i] == 0)
                rowZero = true;
        
        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 < n; i++) {
            if(matrix[0][i] == 0) {
                for(int j = 1; j < m; j++)
                    matrix[j][i] = 0;
            }
        }
        
        for(int i = 1; i < m; i++) {
            if(matrix[i][0] == 0) {
                for(int j = 1; j < n; j++)
                    matrix[i][j] = 0;
            }
        }
        
        if(rowZero) {
            for(int i = 0; i < n; i++)
                matrix[0][i] = 0;
        }
        if(colZero) {
            for(int i = 0; i < m; i++)
                matrix[i][0] = 0;
        }
    }
}