LeetCode 73. 矩阵置零，从标记数组到 O(1) 空间优化彻底讲透

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):mlen(matrix)nlen(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(mn)四、进阶要求O(1) 空间怎么办面试官经常追问不允许额外使用两个数组怎么办这里就要用到经典技巧复用第一行和第一列作为标记数组。五、原地标记法思路利用matrix[i][0]记录第 i 行是否需要清零利用matrix[0][j]记录第 j 列是否需要清零这样就不用额外开空间。需要额外解决的问题第一行和第一列本身也可能有 0。所以要提前记录row0首行是否有 0col0首列是否有 0六、固定四步流程第一步记录首行首列状态row0any(matrix[0][j]0forjinrange(n))col0any(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)。