LeetCode-73.矩阵置零 - sheep44044的小站

矩阵#

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

示例 1：

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

示例 2：

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

空间复杂度O(m+n)的方法

1
func setZeroes(matrix [][]int)  {
2
    m := len(matrix)
3
    n := len(matrix[0])
4
    row := make([]bool, m)
5
    col := make([]bool, n)
6

7
    for i := 0; i < m; i++ {
8
        for j := 0; j < n; j++{
9
            if matrix[i][j] == 0 {
10
                row[i] = true
11
                col[j] = true
12
            }
13
        }
14
    }
15

16
    for i := 0; i < m; i++ {
17
        for j := 0; j < n; j++{
18
            if row[i] == true || col[j] == true {
19
                matrix[i][j] = 0
20
            }
21
        }
22
    }
23

24
}

空间复杂度O(1)的方法

思路：

相较于上个方法，这里把矩阵的第一行和第一列，直接当成上面的 row 和 col 数组来用。

两个疑惑点: 1.为什么可以这样用？ 2.不会影响第一行和列吗？

这里因为如果这个数字下面有0，那么这行/列最后会都会变为0。如果没有就不变。所以拿这个作为row 和 col 数组来用，不会影响这几个数字的结局。
用两个布尔变量 row0Flag 和 col0Flag，去扫一遍第一行和第一列，记下来它们原本到底有没有 0。这样就可以判断原本有没有0。

1
func setZeroes(matrix [][]int)  {
2
    m := len(matrix)
3
    n := len(matrix[0])
4
    row0Flag := false
5
    col0Flag := false
6

7
    for i := 0; i < n; i++ {
8
        if matrix[0][i] == 0 {
9
            row0Flag = true
10
        }
11
    }
12

13
    for i := 0; i < m; i++ {
14
        if matrix[i][0] == 0 {
15
            col0Flag = true
16
        }
17
    }
18

19
    for i := 1; i < m; i++ {
20
        for j := 1; j < n; j++{
21
            if matrix[i][j] == 0 {
22
                matrix[i][0] = 0
23
                matrix[0][j] = 0
24
            }
25
        }
26
    }
27

28
    for i := 1; i < m; i++ {
29
        for j := 1; j < n; j++{
30
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
31
                matrix[i][j] = 0
32
            }
33
        }
34
    }
35

36
    if row0Flag == true {
37
        for i := 0; i < n; i++ {
38
            matrix[0][i] = 0
39
        }
40
    }
41

42
    if col0Flag == true {
43
        for i := 0; i < m; i++ {
44
            matrix[i][0] = 0
45
        }
46
    }
47
}