阿巩
美好的清晨从一道算法开始
为了防止脑壳子生锈,之后也会陆续更新算法相关内容,范围是力扣简单和中等难度的题目。日拱一卒,让我们开始吧!
题目:给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用原地算法。
题解
拿到题目后最直观的思路是扫描两遍matrix,第一遍扫描并记录0的位置;第二遍把对应位置的所在行和列置0。这个解法是需要O(m+n)额外空间的,我们来实现下。
def setZeroes(matrix):
row = len(matrix) # 行
col = len(matrix[0]) # 列
zero_sets = [] # 存放为0的位置
# 找0
for i in range(row):
for j in range(col):
if matrix[i][j] == 0:
zero_sets.append((i, j)) # 将找到的0以元组形式添加到列表中
# 置0
for k, v in zero_sets:
for i in range(row):
matrix[i][v] = 0 # 对应位置的列置0
for j in range(col):
matrix[k][j] = 0 # 对应位置的行置0
return matrix
matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
print(setZeroes(matrix))
# 输出:[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]