一天一道算法题（9）：空间优化从O(mn)到O(1)的思路与实现解析

矩阵置零（LeetCode 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]]

思路分析

难点所在

在遍历矩阵的过程中，如果将遇到的0所在行和列直接变为0，那么后续遍历时，我们无法分辨某个位置的0是原本就有的，还是被我们修改出来的。这会导致错误传播，将原本不该清零的位置也清零了。

解法一：O(mn) 空间（最直观）

最直接的想法是复制一个完全相同的矩阵，然后遍历原矩阵，遇到0就在复制的矩阵中清空对应的行和列。这样我们始终基于原始状态进行操作，避免了错误传播。

funcsetZeroes(matrix[][]int){// 复制矩阵temp:=make([][]int,len(matrix))fori:=0;i<len(matrix);i++{temp[i]=append([]int(nil),matrix[i]...)}// 遍历复制的矩阵，在原矩阵上修改fori:=0;i<len(temp);i++{forj:=0;j<len(temp[i]);j++{iftemp[i][j]==0{// 清空当前行clear(matrix[i])// 清空当前列fork:=0;k<len(matrix);k++{matrix[k][j]=0}}}}}

复杂度分析：

• 时间复杂度：O(mn)，需要遍历矩阵两次
• 空间复杂度：O(mn)，复制了一个完整的矩阵

这种方法虽然直观，但不符合题目对原地算法的要求。

解法二：O(m+n) 空间（改进）

仔细观察，我们其实不需要复制整个矩阵。只需要记录哪些行和哪些列需要清零即可。用两个布尔数组分别标记：

• row[i] = true表示第 i 行需要清零
• col[j] = true表示第 j 列需要清零

funcsetZeroes(matrix[][]int){// 行标记数组row:=make([]bool,len(matrix))// 列标记数组col:=make([]bool,len(matrix[0]))// 第一次遍历：标记需要清零的行和列fori:=0;i<len(matrix);i++{forj:=0;j<len(matrix[0]);j++{ifmatrix[i][j]==0{row[i]=truecol[j]=true}}}// 第二次遍历：根据标记清零fori:=0;i<len(matrix);i++{forj:=0;j<len(matrix[0]);j++{ifrow[i]||col[j]{matrix[i][j]=0}}}}

复杂度分析：

• 时间复杂度：O(mn)
• 空间复杂度：O(m+n)

这种方法比解法一好很多，但仍然不是最优解。

解法三：O(1) 空间（最优解）

能否只使用常量空间？答案是肯定的！

核心思想：利用矩阵的第一行和第一列作为标记数组。

• 用matrix[0][j]标记第 j 列是否需要清零
• 用matrix[i][0]标记第 i 行是否需要清零

但这里有个问题：matrix[0][0]既属于第一行又属于第一列，会产生冲突。解决方案是用两个独立变量row1和col1分别记录第一行和第一列本身是否包含 0。

funcsetZeroes(matrix[][]int){// 用两个变量记录第一行、第一列是否存在 0row1,col1:=1,1// 检查第一行是否有 0forj:=0;j<len(matrix[0]);j++{ifmatrix[0][j]==0{row1=0break}}// 检查第一列是否有 0fori:=0;i<len(matrix);i++{ifmatrix[i][0]==0{col1=0break}}// 遍历除第一行第一列外的所有元素fori:=1;i<len(matrix);i++{forj:=1;j<len(matrix[0]);j++{ifmatrix[i][j]==0{// 用第一行标记列matrix[0][j]=0// 用第一列标记行matrix[i][0]=0}}}// 根据标记清零（除第一行第一列外）fori:=1;i<len(matrix);i++{forj:=1;j<len(matrix[0]);j++{ifmatrix[i][0]==0||matrix[0][j]==0{matrix[i][j]=0}}}// 最后处理第一行ifrow1==0{forj:=0;j<len(matrix[0]);j++{matrix[0][j]=0}}// 最后处理第一列ifcol1==0{fori:=0;i<len(matrix);i++{matrix[i][0]=0}}}

复杂度分析：

• 时间复杂度：O(mn)
• 空间复杂度：O(1)

注意事项：

1. 必须先处理除第一行第一列外的元素，最后再处理第一行和第一列
2. 如果一开始就清零第一行或第一列，会破坏标记信息

总结对比

这道题的核心在于如何用有限的额外空间记录行和列的清零信息。从 O(mn) 到 O(m+n) 再到 O(1)，每一步优化都体现了空间换时间的思想转变，值得细细品味。