矩阵置零

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

示例 1：

img

1
2
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

img

1
2
输入：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(m*n) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗？

最容易想到的方法是开两个数组记录下应该将哪一行和哪一列清零，空间复杂度O(m+n)

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
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> row = new ArrayList<>();
        List<Integer> col = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) { //记录下应该置零的行列
                    row.add(i);
                    col.add(j);
                }
            }
        }
        for (int i : row) { // 把第i行置零
            for (int j = 0; j < n; j++) {
                matrix[i][j] = 0;
            }
        }
        for (int i : col) { // 把第i行置零
            for (int j = 0; j < m; j++) {
                matrix[j][i] = 0;
            }
        }
    }
}

优化空间的思路就是利用原有的空间matrix来代替上面的两个列表，用第0行和第0列标记应该置零的行和列。

但是这样会出现问题，置零的过程会破坏第一行和第一列的值，所以应该从第1行第1列开始修改，最后再判断第0行和第0列中是否有0，进行置零操作

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
39
40
41
42
43
44
45
46
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean rowZero = false;
        boolean colZero = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                    if (i == 0) {
                        rowZero = true;
                    }
                    if (j == 0) {
                        colZero = true;
                    }
                }
            }
        }
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) { // 将第i行置零
                for (int j = 1; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int i = 1; i < n; i++) {
            if (matrix[0][i] == 0) { // 将第i列置零
                for (int j = 1; j < m; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
        if (rowZero) { //将第0行置零
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }
        if (colZero) { //将第0列置零
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}