1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public void setZeroes(int[][] matrix) {
        // 有个问题就是(0, 0)这个元素既记录第0行是否有0, 也记录第0列是否有0, 这样会冲突, 于是
        // 我们单独用一个变量记录第0列是否有0, 那么(0, 0)记录的就是第0行是否有0.
        boolean isColZero = false;
        for (int i = 0; i < matrix.length; i++) {
            // 每一行第0个元素和剩下的元素遇到是0的情况处理的方式不同, 因此单独拎出来处理.
            if (matrix[i][0] == 0)
                isColZero = true;
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // 为什么要倒着遍历? 如果从头开始, 假设第0行之前在标记前出现了0, 那么(0, 0)就会标记为0.
        // 我们往后遍历的时候会发现(0, 0)是0, 表明这一行出现了0, 那么应该第0行全部设置为0, 但是这一行
        // 还记录了其他位置是否有0的情况(也就是第0行有的位置是0, 有的不是0). 从头开始会让第0行记录的信息被覆盖
        // 如果都被设置为0, 那么其他位置看该列情况的时候会发现是0, 但有可能之前这一列并没有0出现.
        // 类似地, 如果第0列
        // 在记录前就有0出现, 那么我们在遍历到每行第0个位置的时候, 会发现isColZero是0, 那么就会把
        // 这个该行第0个位置标记为0, 然而这个位置还记录着当前行是否有0出现, 这样一标记就会让该行其他元素认为
        // 这一行有0出现, 然而实际是可能会有, 可能会没有. 但当我们倒着遍历, 在每一行遍历完后, 第0个元素
        // 的值才会被改变(根据isColZero的值). 这样在每行第0个元素的信息被覆盖前, 该行其他的元素都设置好了.

        for (int i = matrix.length - 1; i >= 0; i--) {
            for (int j = matrix[0].length - 1; j > 0; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (isColZero) {
                matrix[i][0] = 0;
            }
        }
    }
}

简单来说就是第0行记录每一列是否有0出现, 某列有0出现就把第0行该列的那个元素标记为0. 第0列记录每一行是否有0出现, 某行有0出现就把第0列该行的元素标记为0.

问题就是(0, 0)既会记录第0列有没有0, 也会记录第0行有没有0, 因此会混淆. 比如第0行有0但是第0列没有0, 我们就会可能错误地因为看到(0, 0)是0就把第0列全部标记为0. 因此我们使用一个单独的变量来记录第0列是否有0. 这样让(0, 0)来记录第0行是否有0.

还有个问题就是为什么要倒着遍历, 简单来说就是正着遍历会覆盖第0行和第0列记录的每一行每一列的信息. 而倒着遍历则会在某一行的其他元素得到它们需要的信息后才会把该行第0个元素设置为该被设置的值.

时间复杂度: O(m * n)
空间复杂度: O(1)