题目
73. 矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示：- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 – 1
进阶： - 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
- 你能想出一个仅使用常量空间的解决方案吗？
我的代码（Python）
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
rowSet = set()
colSet = set()
m = len(matrix)
n = len(matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
rowSet.add(i)
colSet.add(j)
for rowIdx in rowSet:
matrix[rowIdx] = [0 for _ in range(n)]
for colIdx in colSet:
for i in range(m):
matrix[i][colIdx] = 0 最直观的，额外空间为O(m + n)的算法。还需要优化。
点评
如果考虑边遍历边置位，关键点在于如何分辨原本就是0和后置为0两种情况。前一种需要行列扩展，后一种不需要。所以使用一个缓存空间是很直观的想法。用两个set比起用两个长度各为m和n的列表省了一些空间。
另外可以考虑用一个特殊的标识来暂时替换0，这样第二次遍历时把这个标识换成0就可以了，不过在条件 -2^31 <= matrix[i][j] <= 2^31 – 1 下不太容易实现。在python下用None可以，但是时间效率很低。
官方的解法，实际上是先把第一行和第一列的情况单独处理，然后拿第一行和第一列当成这种标识来处理整个数组。
我自己也往这个向想过，不过想的是额外增加一行或者一列，结果额外空间还是O(m + n)，没有想过单独处理特殊情况的方式。
这是我个人编程和架构设计的一个毛病：总是希望用通用的方式处理所有内容，不做特殊处理。
太执着于这一点，非常不利于工程实现。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog