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]
]
示例 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) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/set-matrix-zeroes
解题思路
- 方法1:额外存储空间方法
如果矩阵中任意一个格子有零我们就记录下它的行号和列号，这些行和列的所有格子在下一轮中全部赋为零。 - 方法2:
- 遍历整个矩阵，如果 cell[i][j] == 0 就将第 i 行和第 j 列的第一个元素标记。
- 第一行和第一列的标记是相同的，都是 cell[0][0]，所以需要一个额外的变量告知第一列是否被标记，同时用 cell[0][0] 继续表示第一行的标记。
- 然后，从第二行第二列的元素开始遍历，如果第 r 行或者第 c 列被标记了，那么就将 cell[r][c] 设为 0。这里第一行和第一列的作用就相当于方法一中的 row_set 和 column_set 。
- 然后我们检查是否 cell[0][0] == 0 ，如果是则赋值第一行的元素为零。
- 然后检查第一列是否被标记，如果是则赋值第一列的元素为零。
代码实现
- 方法1
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
R = len(matrix)
C = len(matrix[0])
rows, cols = set(), set()
for i in range(R):
for j in range(C):
if matrix[i][j] == 0:
rows.add(i)
cols.add(j)
for i in range(R):
for j in range(C):
if i in rows or j in cols:
matrix[i][j] = 0
- 方法2:
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
is_col = False
R = len(matrix)
C = len(matrix[0])
for i in range(R):
if matrix[i][0] == 0:
is_col = True
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 matrix[0][0] == 0:
for j in range(C):
matrix[0][j] = 0
if is_col:
for i in range(R):
matrix[i][0] = 0
