Sui Xin's Blog

[LeetCode]73. 矩阵置零（Set Matrix Zeroes）

Posted on In Disqus:

题目描述

给定一个 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]
]

进阶:

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

解题思路

  1. 解法一：O(n) 空间。将行实时改变，列存储下来最后遍历。
  2. 解法二：O(1) 空间。每一行的第一个数字用来表示这一行是否需要置零，每一列的第一个数字用来表示这一列是否需要置零。用一个单独的变量来表示第一行，否则冲突了。

代码

Python 3.6

解法一：O(n) 空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rows, cols = len(matrix), len(matrix[0])
        coor = set()
        for i in range(rows):
            row_has_0 = False
            for j in range(cols):
                if matrix[i][j] == 0:
                    row_has_0 = True
                    coor.add(j)
                # elif j in coor:
                #     matrix[i][j] = 0
                #     continue
            if row_has_0:
                matrix[i] = [0] * cols
        for j in coor:
            for i in range(rows):
                matrix[i][j] = 0

执行用时 : 240 ms
内存消耗 : 14.3 MB

解法二：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
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rows, cols = len(matrix), len(matrix[0])
        first_row = True if 0 in matrix[0] else False
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == 0:
                    if i > 0:
                        matrix[i][0] = "S"
                    matrix[0][j] = "S"
        
        for i in range(1, rows):
            if matrix[i][0] == "S":
                matrix[i] = [0] * cols
        
        for j in range(cols):
            if matrix[0][j] == "S":
                for i in range(rows):
                    matrix[i][j] = 0
        
        if first_row:
            matrix[0] = [0] * cols

执行用时 : 192 ms
内存消耗 : 14.4 MB

参考

https://leetcode-cn.com/problems/set-matrix-zeroes/solution/ju-zhen-zhi-ling-by-leetcode/

Related Posts