ToB企服应用市场:ToB评测及商务社交产业平台

标题: LeetCode 热题 100 73. 矩阵置零 [打印本页]

作者: 商道如狼道 时间: 5 天前
标题: LeetCode 热题 100 73. 矩阵置零
LeetCode 热题 100 | 73. 矩阵置零

大家好，本日我们来解决一道经典的算法题——矩阵置零。这道题在LeetCode上被标记为中等难度，要求我们将矩阵中为0的元素所在的行和列全部置为0。下面我将分别给出非原地算法和原地算法的Python代码实现，并举行对比分析。

问题形貌

给定一个 m x n 的矩阵，假如一个元素为 0，则将其所在行和列的所有元素都设为 0。
示例：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

复制代码

非原地算法代码

思绪

使用两个额外的数组 rows 和 cols 来记载必要置零的行和列。
遍历矩阵，记载所有值为 0 的元素所在的行和列。
根据记载的行和列，将矩阵中对应的行和列全部置为 0。

代码实现

def setZeroes_non_inplace(matrix):
m, n = len(matrix), len(matrix[0])
rows = [False] * m # 记录需要置零的行
cols = [False] * n # 记录需要置零的列
# 遍历矩阵，记录需要置零的行和列
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
rows[i] = True
cols[j] = True
# 根据记录置零
for i in range(m):
for j in range(n):
if rows[i] or cols[j]:
matrix[i][j] = 0
# 测试示例
matrix1 = [[1,1,1],[1,0,1],[1,1,1]]
matrix2 = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
setZeroes_non_inplace(matrix1)
setZeroes_non_inplace(matrix2)
print(matrix1) # 输出: [[1,0,1],[0,0,0],[1,0,1]]
print(matrix2) # 输出: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

复制代码

原地算法代码

思绪

使用矩阵的第一行和第一列来标记必要置零的行和列。
必要额外处理第一行和第一列本身是否包罗 0。

代码实现

def setZeroes_inplace(matrix):
m, n = len(matrix), len(matrix[0])
first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))
# 使用第一行和第一列来标记是否需要置零
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# 根据标记置零
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# 处理第一行和第一列
if first_row_has_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_has_zero:
for i in range(m):
matrix[i][0] = 0
# 测试示例
matrix1 = [[1,1,1],[1,0,1],[1,1,1]]
matrix2 = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
setZeroes_inplace(matrix1)
setZeroes_inplace(matrix2)
print(matrix1) # 输出: [[1,0,1],[0,0,0],[1,0,1]]
print(matrix2) # 输出: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

复制代码

代码对比

非原地算法

优点：
- 逻辑简朴，易于理解和实现。
- 不必要修改原始矩阵的额外信息。
缺点：
- 使用了额外的空间 O(m + n) 来存储必要置零的行和列。

原地算法

优点：
- 空间复杂度为 O(1)，完全原地操作。
缺点：
- 逻辑稍复杂，必要额外处理第一行和第一列。

总结

非原地算法：逻辑简朴，适合对空间复杂度要求不高的场景。
原地算法：空间复杂度低，适合对空间要求严酷的场景。

根据实际需求选择合适的方法即可。希望这篇题解对大家有所资助，假如有任何问题，欢迎在评论区留言讨论！
关注我，获取更多算法题解和编程技巧！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)