题目

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将这个元素所在的行和列都置零。

点击查看问题跟进。

你有没有使用额外的空间?
使用 O(mn) 的空间不是一个好的解决方案。
使用 O(m + n) 的空间有所改善，但仍不是最好的解决方案。
你能设计一个使用恒定空间的解决方案吗？

思路

使用O（m+n）空间的解法
遍历一遍原数组，使用两个额外数组记录哪些行、列中含有0.
再遍历一遍原数组，把同一行、列含有0的元素置为零。

代码

class Solution {
    public void setZeroes(int[][] matrix) {
        int n =  matrix.length;
        int m = matrix[0].length;

        int[] row = new int[n];
        int[] col = new int[m];

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                if(matrix[i][j] == 0) {
                    row[i] = -1;
                    col[j] = -1;
                }
            }

        for(int i = 0; i < n; i++) 
            for(int j = 0; j < m; j++)
                if(row[i] == -1 || col[j] == -1)
                    matrix[i][j] = 0;
    }
}