题目描述

[EN | CN]

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

示例 1:

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

示例 2:

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

进阶:

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

解法 1:记录索引

一个直接的方法是遍历一遍矩阵,记录需要全置零的行跟列的索引,然后再来真正地赋零。

假设矩阵宽高分别为 $m$、$n$,那么

  • 时间复杂度为 $O(mn)$,遍历两遍;
  • 空间复杂度为 $O(m + n)$,记录需要置零的行跟列。

实现与结果略。

解法 2:借用占位符

为了将空间复杂度降为常数空间,我们尝试在遍历中就解决问题,而不是存起来后面再处理。

我们在遍历的时候,其实就能够给 0 所在的行跟列置零,但是如果直接置零的话会影响后续对元素是否为 0 的判断,因此我们可以将需要置零的元素赋为一个不可能为初始值的值(例如 None),遍历完之后,我们再将 None 替换为 0。

假设矩阵宽高分别为 $m$、$n$,那么

  • 时间复杂度为 $O(mn)$,遍历遍历;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    for k in range(m):
                        if matrix[k][j] != 0:
                            matrix[k][j] = None
                    for k in range(n):
                        if matrix[i][k] != 0:
                            matrix[i][k] = None
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == None:
                    matrix[i][j] = 0
  • 执行用时:60 ms,在所有 Python3 提交中击败了 36.80% 的用户。
  • 内存消耗:14 MB,在所有 Python3 提交中击败了 7.69% 的用户。

解法 3:占位符 + 标志位

其实解法 2 还是有点低效,因为我们在赋 None 的时候,实际上有很多元素被赋了多次。为了避免这种情况,我们能不能想出一种办法,使得我们每行每列只需要赋值一次?

我们可以引入 标志位 的概念,用每一行(或列)中已经访问过的一个元素来表示该行(或列)是否应该全赋零。这个标志位的选取,我们可以直接选每行(和每列)的第一个元素即可。大致步骤如下:

  1. 用两个 bool 值 row1_is_zerocol1_is_zero 分别表示第一行、第一列是否应该赋零,那么之后的操作中第一行与第一列就可以作为对应的列和行的标志位了(比如说索引 [2, 0] 表示第 3 行是否应该全赋零);
  2. 遍历所有元素,对于应该全赋零的行跟列,我们设置其标志位(第一个元素)为 0
  3. 根据遍历后的结果,我们根据标志位来给对应的行和列全赋零(除了第一行跟第一列以外);
  4. 根据 row1_is_zerocol1_is_zero,我们处理第一行跟第一列是否全赋零。

假设矩阵宽高分别为 $m$、$n$,那么

  • 时间复杂度为 $O(mn)$,遍历遍历;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 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
41
42
43
44
45
46
47
48
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])

        # Scan column 1
        col1_is_zero = False
        for i in range(m):
            if matrix[i][0] == 0:
                col1_is_zero = True
                break

        # Scan row 1
        row1_is_zero = False
        for j in range(n):
            if matrix[0][j] == 0:
                row1_is_zero = True
                break

        # Traverse all elements
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0], matrix[0][j] = 0, 0

        # Process rows
        for i in range(1, m):
           if matrix[i][0] == 0:
               for j in range(1, n):
                   matrix[i][j] = 0

        # Process columns
        for j in range(1, n):
           if matrix[0][j] == 0:
               for i in range(1, m):
                   matrix[i][j] = 0

        # Process row 1
        if row1_is_zero:
            for j in range(n):
                matrix[0][j] = 0

        # Process column 1
        if col1_is_zero:
            for i in range(m):
                matrix[i][0] = 0
  • 执行用时:40 ms,在所有 Python3 提交中击败了 97.88% 的用户。
  • 内存消耗:14.1 MB,在所有 Python3 提交中击败了 7.69% 的用户。