0073. 矩阵置零

题目地址(73. 矩阵置零)
​https://leetcode-cn.com/problems/set-matrix-zeroes/​
题目描述
1
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
2
​
3
示例 1:
4
​
5
输入:
6
[
7
  [1,1,1],
8
  [1,0,1],
9
  [1,1,1]
10
]
11
输出:
12
[
13
  [1,0,1],
14
  [0,0,0],
15
  [1,0,1]
16
]
17
示例 2:
18
​
19
输入:
20
[
21
  [0,1,2,0],
22
  [3,4,5,2],
23
  [1,3,1,5]
24
]
25
输出:
26
[
27
  [0,0,0,0],
28
  [0,4,5,0],
29
  [0,3,1,0]
30
]
31
进阶:
32
​
33
一个直接的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
34
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
35
你能想出一个常数空间的解决方案吗？
Copied!
前置知识
状态压缩
公司
阿里
百度
字节
思路
符合直觉的想法是，使用一个 m + n 的数组来表示每一行每一列是否”全部是 0“， 先遍历一遍去构建这样的 m + n 数组，然后根据这个 m + n 数组去修改 matrix 即可。
73.set-matrix-zeroes-1
这样的时间复杂度 O(m * n), 空间复杂度 O(m + n).
代码如下：
1
var setZeroes = function (matrix) {
2
  if (matrix.length === 0) return matrix;
3
  const m = matrix.length;
4
  const n = matrix[0].length;
5
  const zeroes = Array(m + n).fill(false);
6
​
7
  for (let i = 0; i < m; i++) {
8
    for (let j = 0; j < n; j++) {
9
      const item = matrix[i][j];
10
​
11
      if (item === 0) {
12
        zeroes[i] = true;
13
        zeroes[m + j] = true;
14
      }
15
    }
16
  }
17
​
18
  for (let i = 0; i < m; i++) {
19
    if (zeroes[i]) {
20
      matrix[i] = Array(n).fill(0);
21
    }
22
  }
23
​
24
  for (let i = 0; i < n; i++) {
25
    if (zeroes[m + i]) {
26
      for (let j = 0; j < m; j++) {
27
        matrix[j][i] = 0;
28
      }
29
    }
30
  }
31
​
32
  return matrix;
33
};
Copied!
但是这道题目还有一个 follow up， 要求使用 O(1)的时间复杂度。因此上述的方法就不行了。 但是我们要怎么去存取这些信息（哪一行哪一列应该全部为 0）呢？
一种思路是使用第一行第一列的数据来代替上述的 zeros 数组。 这样我们就不必借助额外的存储空间，空间复杂度自然就是 O(1)了。
由于我们不能先操作第一行和第一列， 因此我们需要记录下”第一行和第一列是否全是 0“这样的一个数据，最后根据这个信息去 修改第一行和第一列。
具体步骤如下：
记录下”第一行和第一列是否全是 0“这样的一个数据
遍历除了第一行和第一列之外的所有的数据，如果是 0，那就更新第一行第一列中对应的元素为 0
你可以把第一行第一列看成我们上面那种解法使用的 m + n 数组。
根据第一行第一列的数据，更新 matrix
最后根据我们最开始记录的”第一行和第一列是否全是 0“去更新第一行和第一列即可
73.set-matrix-zeroes-2
关键点
使用第一行和第一列来替代我们 m + n 数组
先记录下”第一行和第一列是否全是 0“这样的一个数据，否则会因为后续对第一行第一列的更新造成数据丢失
最后更新第一行第一列
代码
语言支持：JS，Python3
1
/*
2
 * @lc app=leetcode id=73 lang=javascript
3
 *
4
 * [73] Set Matrix Zeroes
5
 */
6
/**
7
 * @param {number[][]} matrix
8
 * @return {void} Do not return anything, modify matrix in-place instead.
9
 */
10
var setZeroes = function (matrix) {
11
  if (matrix.length === 0) return matrix;
12
  const m = matrix.length;
13
  const n = matrix[0].length;
14
​
15
  // 时间复杂度 O(m * n), 空间复杂度 O(1)
16
  let firstRow = false; // 第一行是否应该全部为0
17
  let firstCol = false; // 第一列是否应该全部为0
18
​
19
  for (let i = 0; i < m; i++) {
20
    for (let j = 0; j < n; j++) {
21
      const item = matrix[i][j];
22
      if (item === 0) {
23
        if (i === 0) {
24
          firstRow = true;
25
        }
26
        if (j === 0) {
27
          firstCol = true;
28
        }
29
        matrix[0][j] = 0;
30
        matrix[i][0] = 0;
31
      }
32
    }
33
  }
34
​
35
  for (let i = 1; i < m; i++) {
36
    for (let j = 1; j < n; j++) {
37
      const item = matrix[i][j];
38
      if (matrix[0][j] == 0 || matrix[i][0] == 0) {
39
        matrix[i][j] = 0;
40
      }
41
    }
42
  }
43
​
44
  // 最后处理第一行和第一列
45
​
46
  if (firstRow) {
47
    for (let i = 0; i < n; i++) {
48
      matrix[0][i] = 0;
49
    }
50
  }
51
​
52
  if (firstCol) {
53
    for (let i = 0; i < m; i++) {
54
      matrix[i][0] = 0;
55
    }
56
  }
57
​
58
  return matrix;
59
};
Copied!
Python3 Code:
直接修改第一行和第一列为 0 的解法：
1
class Solution:
2
    def setZeroes(self, matrix: List[List[int]]) -> None:
3
        """
4
        Do not return anything, modify matrix in-place instead.
5
        """
6
        def setRowZeros(matrix: List[List[int]], i:int) -> None:
7
            C = len(matrix[0])
8
            matrix[i] = [0] * C
9
​
10
        def setColZeros(matrix: List[List[int]], j:int) -> None:
11
            R = len(matrix)
12
            for i in range(R):
13
                matrix[i][j] = 0
14
​
15
        isCol = False
16
        R = len(matrix)
17
        C = len(matrix[0])
18
​
19
        for i in range(R):
20
            if matrix[i][0] == 0:
21
                isCol = True
22
            for j in range(1, C):
23
                if matrix[i][j] == 0:
24
                    matrix[i][0] = 0
25
                    matrix[0][j] = 0
26
        for j in range(1, C):
27
            if matrix[0][j] == 0:
28
                setColZeros(matrix, j)
29
​
30
        for i in range(R):
31
            if matrix[i][0] == 0:
32
                setRowZeros(matrix, i)
33
​
34
        if isCol:
35
            setColZeros(matrix, 0)
Copied!
另一种方法是用一个特殊符合标记需要改变的结果，只要这个特殊标记不在我们的题目数据范围（0 和 1）即可，这里用 None。
1
class Solution:
2
    def setZeroes(self, matrix: List[List[int]]) -> None:
3
        """
4
        这题要解决的问题是，必须有个地方记录判断结果，但又不能影响下一步的判断条件；
5
        直接改为0的话，会影响下一步的判断条件；
6
        因此，有一种思路是先改为None，最后再将None改为0；
7
        从条件上看，如果可以将第一行、第二行作为记录空间，那么，用None应该也不算违背题目条件；
8
        """
9
        rows = len(matrix)
10
        cols = len(matrix[0])
11
        # 遍历矩阵，用None记录要改的地方，注意如果是0则要保留，否则会影响下一步判断
12
        for r in range(rows):
13
            for c in range(cols):
14
                if matrix[r][c] is not None and matrix[r][c] == 0:
15
                    # 改值
16
                    for i in range(rows):
17
                        matrix[i][c] = None if matrix[i][c] != 0 else 0
18
                    for j in range(cols):
19
                        matrix[r][j] = None if matrix[r][j] != 0 else 0
20
        # 再次遍历，将None改为0
21
        for r in range(rows):
22
            for c in range(cols):
23
                if matrix[r][c] is None:
24
                    matrix[r][c] = 0
Copied!
复杂度分析
时间复杂度：$O(M * N)$
空间复杂度：$O(1)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
​
扩展
为什么选择第一行第一列，选择其他行和列可以么？为什么？

最近更新 1yr ago

复制链接

内容