【刷题日记】73. 矩阵置零

一、题目描述：

今天来做一个二维数组的题目，矩阵置零

二、这道题考察了什么思想？你的思路是什么？

题目对我们的要求很明确也很简单，需要我们根据条件，将题目给出的二维矩阵对应的位置修改为 0

条件是：

当原矩阵的的某个位置数字为 0 的时候，那么这个位置对应的一行，和一列全部都需要变成 0

分析

这个题目看的出来，相对比较简单，而且看完题目，相信我们很快就会有思路，可能不是最优解，范式至少我们能够第一时间想出解决的方式，例如

看到题目，就能很容易想到，既然需要在原矩阵上修改值，那么我们就不能每一步都读取原有矩阵来判断是否需要按照条件来将矩阵的行列变成 0 ， 因此我们需要用一个相应的一维数组来标记一下某一行是否需要全 0，某一列是否需要全 0

例如示例二中：

我们就需要这样的两个一维数组来进行标记

那么当我们遍历二维矩阵的时候，实际上去校验一下当前位置对应的行或者列是否需要全部为 0 ，若是，则将当前位置的数值赋值为 0 即可

其实到这里，我们本应就可以编码了，但是我们继续看题，题目需要我们用更小的空间复杂度来解决这个题，因为本次我们第一时间想到的方式，空间复杂度是 O(m+n)，其中 m 为行数组，n 为列数组的空间

进阶

那我们就要办法优化一下空间复杂度，既然上述我们是用了两个一维数组来进行标记，那么我们为了降低时间复杂度，是否可以用两个变量来标记呢？思考思考

还是以示例 2 为例：

1. 我们遍历二维矩阵，记录一下当前矩阵的第一行，第一列是否需要为 0 ，记录为 row0 和 col0，很明显，该示例的记录结果为

2. 我们开始遍历二维矩阵，判断当前位置是否为 0 ，若为零，则将原二维矩阵对应的第 0 行，和第0 列对应的位置赋值为 0 ，例如得到如下结果，发现对于本案例没啥变化，这一步主要是为了给我们的第0 行 和第 0 列进行赋值的

3. 再遍历一次二维矩阵，这个时候，我们校验的是，当前的位置对应的第 0 行，和第0 列对应的位置是否为 0 ，若是，则将当前位置赋值为 0，得到如下结果

4. 判断 row0 ，和 col0 是否为 true，若是，则将第 0 行 或者第0 列全部赋值为 0，这个是表示最开始原矩阵中就需要将第 0 行或的第 0 列全部赋值为 0 ，放在现在才做，是为了不影响前面步骤的进行， 得到如下结果

看到这里，xdm 应该看明白了这种方式了，我们只引入了常数级别的空间消耗，满足题目的进阶要求，一起来撸代码吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

• 严格按照上述分析的步骤来，不能跳步骤，直接翻译成代码即可

编码如下：

func setZeroes(matrix [][]int)  {
    // 先初始化我们的行列标记，标记第一行和第一列是否有 0
    n, m := len(matrix), len(matrix[0])
    row0, col0 := false, false
     for _, v := range matrix[0] {
        if v == 0 {
            row0 = true
            break
        }
    }
    for _, r := range matrix {
        if r[0] == 0 {
            col0 = true
            break
        }
    }
    // 开始正式遍历二维矩阵，查看当前数字是否为 0， 若为 0 ，则把当前位置对应第 0 行 和第 0 列 赋值为 0
     for i := 1; i < n; i++ {
        for j := 1; j < m; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }
    // 再遍历 1 次二维矩阵，校验到当前位置对应的第 0 行，或者第 0 列是 0 ，则当前位置直接赋值为 0
    for i := 1; i < n; i++ {
        for j := 1; j < m; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }
    // 最后，我们确认一下最开始我们校验的第 0 行 和 第 0 列是不是一开始就是有 0，若有，则这一行，或者这一列都是赋值为 0
    if row0 {
        for j := 0; j < m; j++ {
            matrix[0][j] = 0
        }
    }
    if col0 {
        for _, r := range matrix {
            r[0] = 0
        }
    }
}

四、总结：

本次解法文章内容中也有说到，空间复杂度是 O(1) ，这个就不过多说明， 时间复杂度也是很明确的，我们最多就是遍历了二维矩阵，因此时间复杂度是 O(mn) ，m 为行，n 为列

原题地址：73. 矩阵置零

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~