 空间优化彻底讲透)
LeetCode 73. 矩阵置零，从标记数组到 O(1) 空间优化彻底讲透
一、题目描述
给定一个 m × n 的矩阵，如果一个元素为 0，则将其所在行和所在列的所有元素都设为 0。
要求：
- 原地修改矩阵
- 尽量减少额外空间使用
示例：
输入：[[1,1,1],[1,0,1],[1,1,1]]输出：[[1,0,1],[0,0,0],[1,0,1]]二、最容易想到的错误做法
很多人第一次做这题都会这样写：
foriinrange(m):forjinrange(n):ifmatrix[i][j]==0:将该行该列全部置零这种写法是错误的。
原因在于：
当你把某行某列置零后，新产生的 0 又会被后续遍历当作原始 0 继续扩散。
例如：
111101111处理中间的 0 后：
101000101此时新增的多个 0 如果继续参与判断，就会导致整个矩阵最终全部变成 0。
因此：
必须先记录哪些行列需要置零，再统一修改。
三、解法一：标记数组法
核心思想
分别记录：
- 哪些行需要置零
- 哪些列需要置零
遍历结束后统一处理。
第一步：创建标记数组
rows=[False]*m cols=[False]*n例如：
111101111发现：
matrix[1][1]==0则：
rows[1]=Truecols[1]=True表示：
- 第 1 行要清零
- 第 1 列要清零
第二步：统一置零
再次遍历矩阵：
ifrows[i]orcols[j]:matrix[i][j]=0完整代码
classSolution:defsetZeroes(self,matrix):m=len(matrix)n=len(matrix[0])rows=[False]*m cols=[False]*nforiinrange(m):forjinrange(n):ifmatrix[i][j]==0:rows[i]=Truecols[j]=Trueforiinrange(m):forjinrange(n):ifrows[i]orcols[j]:matrix[i][j]=0复杂度分析
时间复杂度：
O(m*n)空间复杂度：
O(m+n)四、进阶要求：O(1) 空间怎么办？
面试官经常追问：
不允许额外使用两个数组怎么办？
这里就要用到经典技巧：
复用第一行和第一列作为标记数组。
五、原地标记法
思路
利用：
matrix[i][0]记录第 i 行是否需要清零
利用：
matrix[0][j]记录第 j 列是否需要清零
这样就不用额外开空间。
需要额外解决的问题
第一行和第一列本身也可能有 0。
所以要提前记录：
row0首行是否有 0
col0首列是否有 0
六、固定四步流程
第一步：记录首行首列状态
row0=any(matrix[0][j]==0forjinrange(n))col0=any(matrix[i][0]==0foriinrange(m))第二步：利用首行首列打标记
foriinrange(1,m):forjinrange(1,n):ifmatrix[i][j]==0:matrix[i][0]=0matrix[0][j]=0第三步：处理中间区域
foriinrange(1,m):forjinrange(1,n):ifmatrix[i][0]==0ormatrix[0][j]==0:matrix[i][j]=0第四步：处理首行首列
ifrow0:首行全部置零ifcol0:首列全部置零七、高频易错点
错误1：边遍历边置零
会导致新增 0 被重复扩散。
错误2：没先保存首行首列状态
首行首列后续要充当标记区。
如果提前被覆盖，原始信息就丢失了。
错误3：忘记最后处理首行首列
这是 O(1) 解法最常见 Bug。
八、一句话总结
矩阵置零的核心不是如何置零，而是如何保存原始的零信息。
普通做法使用两个标记数组记录行列状态，进阶做法则直接复用第一行和第一列作为标记区，将空间复杂度优化到 O(1)。
