长大后想做什么？做回小孩！

0%

LeetCode——矩阵置零

发表于 分类于 Valine：
本文字数： 267

NO.73 矩阵置零 中等

8g0fjU.png

8g0WcT.png

没有想出来题目中说的最糟糕的空间(mn)是怎么做的，再申请一个大小一样的数组么？

思路一：集合记录

第一次遍历，用两个set分别记录值为0的元素的行和列。

第二次遍历，将两个set记录的行和列上的元素置为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void setZeroes(int[][] matrix) {
    Set<Integer> row=new HashSet<>(),col=new HashSet<>();
    int m = matrix.length,n=matrix[0].length;
    //第一次遍历，统计值为0的元素的行和列
    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);
            }
        }
    }
    //第二次遍历，将两个set记录的行列上的元素置为0
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (row.contains(i)||col.contains(j))matrix[i][j]=0;
        }
    }
}

时间复杂度：O(mn) 两次遍历

空间复杂度：O(m+n)

思路二：矩阵自身替代Set

在上面的方法中我们利用额外空间去记录需要置零的行号和列号，通过修改原始矩阵可以避免额外空间的消耗。 具体过程看图结合代码更清晰：

8ghVM9.png

8ghAxJ.png

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
public void setZeroes(int[][] matrix) {
    boolean flag_0row = false, flag_0col = false;
    int m = matrix.length, n = matrix[0].length;
    //检查第一行、第一列是否有0,
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) {
            flag_0col = true;
            break;
        }
    }
    for (int i = 0; i < n; i++) {
        if (matrix[0][i] == 0) {
            flag_0row = true;
            break;
        }
    }
    //遍历除了第一列和第一行之外的其余所有元素
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
        }
    }
    //再次遍历除了第一列和第一行之外的其余所有元素
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
        }
    }
    //检查flag
    if (flag_0row) {
        for (int i = 0; i < n; i++) {
            matrix[0][i] = 0;
        }
    }
    if (flag_0col) {
        for (int i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
}

时间复杂度：O(mn)

空间复杂度：O(1)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github