Leetcode 73：矩阵置零（最详细的解法！！！）

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

示例 1:

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]
1
2
3
4
5
6
7
8
9
10
11
12

示例 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]
]
1
2
3
4
5
6
7
8
9
10
11
12

进阶:

• 一个直接的解决方案是使用 O(m**n) 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个常数空间的解决方案吗？

解题思路

一个最简答的思路就是通过遍历矩阵的每一个元素，判断这个元素是不是0，如果是的话那么将对应的行和列的元素置为零，但是这种有一个陷阱，因为一旦置为零，那么我们对于没有遍历到的元素就会存在这样的风险：原先不是0，但是因为之前有数将其置为0了，我们遍历到这个原本是非0数的时候就不要将其行和列置为零了。为例解决这个问题，我们需要重新开辟一个矩阵大小的空间用来存储最后的0。

from copy import deepcopy
class Solution:
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        if not matrix:
            return
        r, c = len(matrix), len(matrix[0])
        mat = deepcopy(matrix)

        for i in range(r):
            for j in range(c):
                if mat[i][j] == 0:
                    for m in range(r):
                        matrix[m][j] = 0
                    for n in range(c):
                        matrix[i][n] = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注意这里要使用deepcopy，因为是两层的list结构。

有没有更好的做法呢？就像进阶中提到的，我们是不是有空间复杂度更小的做法。我们可以这样考虑，例如

对于第一行和第一列元素我们单独考虑。我们首先开始遍历除第一行第一列外的所有元素，当我们碰到0，也就是2,2这个点，所以我们将之前的同一行同一列的第一行和第一列置为0

接着我们根据第一行和第一列的0和非0将矩阵的（除了第一行第一列）行和列全置为0

我们接着要考虑第一行第一列的问题，如果第一行第一列一开始就有0的话（(0,0)、(2,0)），我们将对应行列（第一行第一列）置为0即可。

我们通过这个算法，就可以使用O(1)的空间复杂度解决这个问题。

class Solution:
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        if not matrix:
            return
        r, c, flagr, flagc = len(matrix), len(matrix[0]), False, False
        for i in range(r):
            if matrix[i][0] == 0:
                flagr = True
                
        for j in range(c):
            if matrix[0][j] == 0:
                flagc = True
                    
        for i in range(1, r):
            for j in range(1, c):
                if matrix[i][j] == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        for i in range(1, r):
            for j in range(1, c):
                if not matrix[i][0] or not matrix[0][j]:
                    matrix[i][j] = 0

        if flagc:
            for j in range(c):
                matrix[0][j] = 0

        if flagr:
            for i in range(r):
                matrix[i][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

一种更加简洁的写法

class Solution:
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        if not matrix:
            return
        
        r, c, flag = len(matrix), len(matrix[0]), False               
        for i in range(r):
            if matrix[i][0] == 0:
                flag = True
            for j in range(1, c):
                if matrix[i][j] == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        for i in range(r-1, -1, -1):
            for j in range(c-1, 0, -1):
                if not matrix[i][0] or not matrix[0][j]:
                    matrix[i][j] = 0
            if flag:
                matrix[i][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

基本思想同上，我们只需考虑第一列，然后遍历的过程中采用自底向上即可。

reference:

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

https://leetcode.com/problems/set-matrix-zeroes/discuss/26014/Any-shorter-O(1)-space-solution

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！