LeetCode刷题实战73：矩阵置零-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 矩阵置零，我们先来看题面：

https://leetcode-cn.com/problems/set-matrix-zeroes/

Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

题意

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

样例

示例 1:

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

解题

https://www.cnblogs.com/techflow/p/13035521.html

近在眼前的解法原来是坑

这题的题意非常简单，解法也非常明显，以至于很多人拿到它都会当做模拟题来解决。即遍历一下数组，如果找到0，那么将它所在的行和列赋值为0，然后继续遍历。

这段逻辑并不难写，我们很容易写出来：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        if n == 0:
            return
        
        m = len(matrix[0])
        for i in range(n):
            for j in range(m):
                # 当我们找到为0的位置之后，将所在的行和列置为0
                if matrix[i][j] == 0:
                    for k in range(m):
                        matrix[i][k] = 0
                    for k in range(n):
                        matrix[k][j] = 0

但是很遗憾的是，这样的做法是错误的，实际上连样例都无法通过。通不过样例的原因也很简单，因为0具有传递性。

举个简单的例子，假设第0行当中有一个0，那么最后的结果一定是第0行全部被置为0。但问题是我们是在遍历到0的时候来进行的set操作，这样会将第0行的其他元素也置为0。这样当我们遍历到后面的位置之后，会继续传递，从而将一些不该置为0的地方也置为0了。

举个简单的例子，比如：第0行是1 0 0 1。显然由于第0行存在0，所以操作之后的结果一定是全为0。但问题是matrix[0][3]这个位置原本并不为0，但是如果我们在发现matrix[0][1]为0的时候，将它置为0的话，那么当我们后面遍历到matrix[0][3]得到0的时候，会无法判断究竟是这个位置原本就是0，还是前面出现了0导致这一行全部变成了0。这两者的操作是不同的。

眼看着目标就在眼前，好像一伸手就碰得到，但是偏偏好像这一步就是咫尺天涯，怎么也碰不到。这种感觉想想都很难受，我想，当你试着用这种方法去解这道题然后发现不行的时候，一定会有这样的感觉。并且你会发现好像也没有什么很好的办法来优化。

这种情况在正式的算法比赛当中经常遇到，所以专业的竞赛选手有了经验（吃过亏）之后，想出思路的第一时间就会立即转向思考，这样做是不是会有什么坑，或者是考虑不到的情况。严谨一点的同学还会构思几组不同的测试数据进行测试，或者是脑海中模拟算法的运算。

刚不过去只能绕

以前我年轻的时候总是不信邪，有时候明知道这个方法并不好，或者是存在反例，但是仍会坚持想要通过自己的努力想出一个方案来解决它，而不是更换方法。

我不知道有多少人有同样的想法，但是一般来说头铁的毛病最后总是会被治好的。这题算是一个不错的例子，如果你坚持使用模拟的方法来做这道题，只有一种方案就是再创建一个同样大小的数组来作为缓存。当我们遇到0的时候，我们不直接修改原数组中的结果，而是修改缓存，将同行和同列缓存数组中的元素置为0，最后再将缓存数组与原数组合并。

但是显然这不是一种好的方法，因为题目要求in-place的目的就是为了节约空间，我们另外创建了一个同样大小的数组显然违背了题目的本意。

所以头铁到最后还是得认清现状，这个方法不适合这道题，需要更换解法。如果是在比赛当中得出的这个结论，那么很有可能奖牌已经和你没什么关系了。坚持和固执本身也许没有太大的区别，可能只是出现的场景不一样。

进阶解法

回到这道题本身，我们已经证明了模拟的思路是行不通的，除了一边遍历一边操作可能带来的混乱之外，还有一个点是这样的复杂度很高。因为如果原数据当中如果本身0就很多的话，那么我们会需要不停地操作，极端情况下，如果所有元素都是0，那么我们每一个位置都需要操作一下行列，整体的复杂度会达到

。

既然如此，还有什么好的办法吗？

当然是有的，其实也挺明显的，因为对于一个出现的0来说它会影响的范围是固定的，就是所在的行和列，那我们是不是记录下会全部置为0的行和列，最后再遍历一遍数据，看下当前元素是不是出在置为0的范围当中就可以了。这种方法需要我们再创建两个数组，用来存储行和列是否被置为0。

这个解法也很直观，想到了代码应该不难写：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        if n == 0:
            return
        
        m = len(matrix[0])
        rows = [0 for _ in range(n)]
        cols = [0 for _ in range(m)]
        
        # 记录置为0的行和列
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == 0:
                    rows[i], cols[j] = 1, 1
                    
        # 如果所在行或者列置为0，那么当前位置为0
        for i in range(n):
            for j in range(m):
                if rows[i] or cols[j]:
                    matrix[i][j] = 0

终极解法

上面的做法虽然通过之后的战绩不太光彩，没能战胜90%以上的提交，但是能够通过，而且算法没有数量级的差距，也算是可以的。如果让我来做，我可能就想到这种方法为止了。但是题目当中明确说了，还有空间复杂度为O(1)的算法，逼得我进一步思考了一下。

一般来说我们都是优化时间复杂度，很少会优化空间复杂度。相比于优化时间，优化空间有时候更加困难。因为有些时候我们可以空间换时间，可以预处理，可以离线计算……方法相对比较多。但优化空间的方法则很少，尤其是很多时候还不能牺牲时间，所以一般来说只能从算法本身来优化，很少有什么套路可以套用。

在这个问题当中，要优化空间复杂度到常数级，那么说明我们连数组都不能用。也就是说不能记录行和列的信息，但是我们也不能用模拟的方法来进行，那么应该怎么办呢？

干想是很难想出来的，但是我们换个思路，问题就完全不一样了。上面的算法时间复杂度是最优的，空间复杂度不太行，那么有没有办法既使用同样的算法，又能节省空间呢？看起来似乎不可能，但是其实可以，方法说穿了也并不值钱，就是将数据想办法存在已有的地方，而不是另外开辟空间。在这个问题当中，已有的地方当然就只有一个就是原数组。也就是说我们要把每一行和列是否为0的信息记录在原数组当中，比如我们可以把第0行和第0列用来做这个事情。

但这样又会带来另外一个问题，如果第0行和第0列本身当中也有0出现该怎么办？没办法，只能特判了。我们单独用变量来记录第0行和第0列是否被置为0，这样我们就最大化地利用了空间，将空间复杂度降低到了常数级。

代码逻辑和上面一脉相承，只是多了一点骚操作。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        if n == 0:
            return
        
        m = len(matrix[0])
        
        row, col = False, False
        
        # 特判0，0的位置
        if matrix[0][0] == 0:
            row, col = True, True
        
        # 特判第0列是否含0
        for i in range(n):
            if matrix[i][0] == 0:
                col = True
                break
                
        # 特判第0行是否含0
        for i in range(m):
            if matrix[0][i] == 0:
                row = True
                break
                
        # 将i行，j列是否为0的信息存入matrix当中
        for i in range(0, n):
            for j in range(0, m):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
                    
        for i in range(1, n):
            for j in range(1, m):
                # 根据第0行与第0列数据还原
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
                  
        # 最后处理第0行与第0列
        if row:
            for i in range(m):
                matrix[0][i] = 0
                
        if col:
            for i in range(n):
                matrix[i][0] = 0