难度: Medium
编写一种算法，若M × N矩阵中某个元素为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] ]
Submission
运行时间: 23 ms
内存: 16.9 MB
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
N = len(matrix)
M = len(matrix[0])
row = []
col = []
for i in range(N):
for j in range(M):
if matrix[i][j] == 0:
row.append(i)
col.append(j)
for i in list(set(row)):
for k in range(M):
matrix[i][k] = 0
for j in list(set(col)):
for k in range(N):
matrix[k][j] = 0
Explain
此题解的思路是首先遍历整个矩阵，记录下所有值为0的元素的行号和列号。利用两个列表分别存储这些行号和列号。在记录行号和列号后，利用集合去重，然后遍历这些唯一的行号，将对应的每一行的所有元素设置为0。接着，遍历这些唯一的列号，将对应的每一列的所有元素设置为0。这样可以确保所有应该被清零的行和列都被正确处理。
时间复杂度: O(N*M)
空间复杂度: O(N + M)
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
N = len(matrix) # 获取矩阵的行数
M = len(matrix[0]) # 获取矩阵的列数
row = [] # 存储含零元素的行索引
col = [] # 存储含零元素的列索引
for i in range(N):
for j in range(M):
if matrix[i][j] == 0: # 检测元素是否为0
row.append(i) # 记录行索引
col.append(j) # 记录列索引
for i in list(set(row)): # 去重并遍历行索引
for k in range(M):
matrix[i][k] = 0 # 将行中的所有元素设为0
for j in list(set(col)): # 去重并遍历列索引
for k in range(N):
matrix[k][j] = 0 # 将列中的所有元素设为0
Explore
在遍历矩阵时，同时记录行号和列号是因为一旦矩阵中的某个元素为0，那么不仅整个行需要被置为0，其所在的列也需要被置为0。如果只记录行号或只记录列号，我们将无法完成题目要求的将元素所在行和列都置0的操作。例如，如果我们只记录行号，那么虽然能将所有包含0的行置为0，但无法处理那些因为同一行中不同元素所在的不同列也应该被置为0的情况。因此，同时记录行号和列号可以确保我们有足够的信息来正确修改整个矩阵。
使用集合去除重复值主要是为了优化接下来将行和列置为0的操作的效率。如果不去除重复值，那么在后续的操作中可能会对同一行或列重复执行置0的操作，这样不仅增加了不必要的计算量，还降低了算法的总体效率。通过使用集合去除重复的行号和列号，我们可以确保每一行和每一列只被置为0一次，从而优化了执行时间和减少了不必要的操作。
如果不使用集合去除行号和列号的重复值，则在将行和列设为0的过程中的确可能出现对同一行或列重复操作的情况。这是因为如果矩阵中多个元素为0且它们位于同一行或列，我们可能会多次记录这一行或列。为了优化，我们使用集合来去除这些重复值，确保每一行和每一列只处理一次，从而避免了重复操作。这样不仅提升了算法的效率，还节省了运行时间。