LeetCode 热题 100 73. 矩阵置零

LeetCode 热题 100 | 73. 矩阵置零

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

---

问题形貌

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

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

复制代码

---

非原地算法代码

思绪

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

代码实现

1. def setZeroes_non_inplace(matrix):
2.     m, n = len(matrix), len(matrix[0])
3.     rows = [False] * m  # 记录需要置零的行
4.     cols = [False] * n  # 记录需要置零的列
6.     # 遍历矩阵，记录需要置零的行和列
7.     for i in range(m):
8.         for j in range(n):
9.             if matrix[i][j] == 0:
10.                 rows[i] = True
11.                 cols[j] = True
13.     # 根据记录置零
14.     for i in range(m):
15.         for j in range(n):
16.             if rows[i] or cols[j]:
17.                 matrix[i][j] = 0
19. # 测试示例
20. matrix1 = [[1,1,1],[1,0,1],[1,1,1]]
21. matrix2 = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
23. setZeroes_non_inplace(matrix1)
24. setZeroes_non_inplace(matrix2)
26. print(matrix1)  # 输出: [[1,0,1],[0,0,0],[1,0,1]]
27. print(matrix2)  # 输出: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

复制代码

---

原地算法代码

思绪

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

代码实现

1. def setZeroes_inplace(matrix):
2.     m, n = len(matrix), len(matrix[0])
3.     first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
4.     first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))
6.     # 使用第一行和第一列来标记是否需要置零
7.     for i in range(1, m):
8.         for j in range(1, n):
9.             if matrix[i][j] == 0:
10.                 matrix[i][0] = 0
11.                 matrix[0][j] = 0
13.     # 根据标记置零
14.     for i in range(1, m):
15.         for j in range(1, n):
16.             if matrix[i][0] == 0 or matrix[0][j] == 0:
17.                 matrix[i][j] = 0
19.     # 处理第一行和第一列
20.     if first_row_has_zero:
21.         for j in range(n):
22.             matrix[0][j] = 0
24.     if first_col_has_zero:
25.         for i in range(m):
26.             matrix[i][0] = 0
28. # 测试示例
29. matrix1 = [[1,1,1],[1,0,1],[1,1,1]]
30. matrix2 = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
32. setZeroes_inplace(matrix1)
33. setZeroes_inplace(matrix2)
35. print(matrix1)  # 输出: [[1,0,1],[0,0,0],[1,0,1]]
36. print(matrix2)  # 输出: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

复制代码

---

代码对比

非原地算法

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

原地算法

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

---

总结

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

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

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