37.矩阵置零

题目

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

示例:

输入: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

进阶:

一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。

你能想出一个仅使用常量空间的解决方案吗？

思路

思路一: 用 O(m+n)额外空间

两遍扫matrix,第一遍用集合记录哪些行,哪些列有0;第二遍置0

class Solution {
    public void setZeroes(int[][] matrix) {
        Set<Integer> row_zero = new HashSet<>();
        Set<Integer> col_zero = new HashSet<>();
        int row = matrix.length;
        int col = matrix[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    row_zero.add(i);
                    col_zero.add(j);
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (row_zero.contains(i) || col_zero.contains(j)) matrix[i][j] = 0;
            }
        }  
    }
}

思路二: 用O(1)空间

关键思想: 用matrix第一行和第一列记录该行该列是否有0,作为标志位

上面方法一的标记数组需要额外开O(m + n)空间，能不能把标记直接存在矩阵内部?

可以用矩阵第一行的数据来标记对应的列是不是0，用第一列数据标记对应的行是不是0:

matrix[0][j] == 0 标识第 j 列需要置零
matrix[i][0] == 0 标识第 i 行需要置零

这样就不用额外数组了。

但是这样会有一个新的问题，就是第一行和第一列的置零信息会冲突-- matrix[0][0]既属于第一行又属于第一列，一个格子存不下两份信息。

所以第一列要设置一个标志位,为了防止自己这一行(一列)也有0的情况.注释写在代码里,直接看代码很好理解!

第一次循环:

0行数组的每个元素临时标识该元素所在列是否有0，0列数组的每个元素临时标识该元素所在行是否有0。
判断每行的第0列是否为0，有则赋值额外的标识字段，该字段的作用是用于后续对称遍历的时候，赋值所有行的0列是否应该赋值0使用

比如原始数组为
[
    [2,1,2,3],
    [2,1,2,3],
    [3,0,5,2],
    [1,3,0,5]
]


// 如果当前遍历位置为0，则该行0列设置标识，以便后续使用
// 如果当前遍历位置为0，则0行该列设置标识，以便后续使用
[
    [2,0,0,3],
    [2,1,2,3],
    [0,0,5,2],
    [0,3,0,5]
]
// 第二次循环-从右下角遍历处理：行从最后一行遍历（直到0行），列从最后一列遍历(直到第一列)
// 使用0行数组、0列数组判断当前遍历位置是否应该置0
// 注意需要额外使用标识字段判断该行0列是否应该置0
// 处理完成之后
[
    [2,0,0,3],
    [2,0,0,3],
    [0,0,0,0],
    [0,0,0,0]
]

这里还有一个问题要注意就是为什么第二遍遍历的时候也要从后往前(倒序)?

因为首行matrix[0][j]和首列matrix[i][0]是标记，要到最后才能动他们。

如果从前往后就会把首行首列的标记覆盖掉，导致后面的格子读不到正确的标记。

所以从后往前开始就能保证在读取matrix[i][0]和matrix[0][j]这些标记时，他们还没有被修改。

class Solution {
    fun setZeroes(matrix: Array<IntArray>): Unit {
        val row = matrix.size
        val colum = matrix[0].size

        var firstColumnZero = false

        for (i in 0 until row) {
            for (j in 0 until colum) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0
                    if (j == 0) {
                        firstColumnZero = true
                    } else {
                        matrix[0][j] = 0
                    }
                }
            }
        }

        for (i in row - 1 downTo 0) {
            // 不处理第一列
            for (j in colum - 1 downTo 1) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0
                }
            }
            // 要在循环外，且只影响第一列
            if (firstColumnZero) {
                matrix[i][0] = 0
            }
        }
    }
}


class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        boolean row0_flag = false;
        boolean col0_flag = false;
        // 第一行是否有零
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                row0_flag = true;
                break;
            }
        }
        // 第一列是否有零
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                col0_flag = true;
                break;
            }
        }
        // 把第一行第一列作为标志位
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 置0
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (row0_flag) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0_flag) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        } 
    }
}

下一题

邮箱：charon.chui@gmail.com
Good Luck!