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

矩阵置零LeetCode 73题三种解法详解文章目录矩阵置零LeetCode 73题三种解法详解题目描述思路分析难点所在解法一O(mn) 空间最直观解法二O(mn) 空间改进解法三O(1) 空间最优解总结对比题目描述给定一个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;ilen(matrix);i{temp[i]append([]int(nil),matrix[i]...)}// 遍历复制的矩阵在原矩阵上修改fori:0;ilen(temp);i{forj:0;jlen(temp[i]);j{iftemp[i][j]0{// 清空当前行clear(matrix[i])// 清空当前列fork:0;klen(matrix);k{matrix[k][j]0}}}}}复杂度分析时间复杂度O(mn)需要遍历矩阵两次空间复杂度O(mn)复制了一个完整的矩阵这种方法虽然直观但不符合题目对原地算法的要求。解法二O(mn) 空间改进仔细观察我们其实不需要复制整个矩阵。只需要记录哪些行和哪些列需要清零即可。用两个布尔数组分别标记row[i] true表示第 i 行需要清零col[j] true表示第 j 列需要清零funcsetZeroes(matrix[][]int){// 行标记数组row:make([]bool,len(matrix))// 列标记数组col:make([]bool,len(matrix[0]))// 第一次遍历标记需要清零的行和列fori:0;ilen(matrix);i{forj:0;jlen(matrix[0]);j{ifmatrix[i][j]0{row[i]truecol[j]true}}}// 第二次遍历根据标记清零fori:0;ilen(matrix);i{forj:0;jlen(matrix[0]);j{ifrow[i]||col[j]{matrix[i][j]0}}}}复杂度分析时间复杂度O(mn)空间复杂度O(mn)这种方法比解法一好很多但仍然不是最优解。解法三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;jlen(matrix[0]);j{ifmatrix[0][j]0{row10break}}// 检查第一列是否有 0fori:0;ilen(matrix);i{ifmatrix[i][0]0{col10break}}// 遍历除第一行第一列外的所有元素fori:1;ilen(matrix);i{forj:1;jlen(matrix[0]);j{ifmatrix[i][j]0{// 用第一行标记列matrix[0][j]0// 用第一列标记行matrix[i][0]0}}}// 根据标记清零除第一行第一列外fori:1;ilen(matrix);i{forj:1;jlen(matrix[0]);j{ifmatrix[i][0]0||matrix[0][j]0{matrix[i][j]0}}}// 最后处理第一行ifrow10{forj:0;jlen(matrix[0]);j{matrix[0][j]0}}// 最后处理第一列ifcol10{fori:0;ilen(matrix);i{matrix[i][0]0}}}复杂度分析时间复杂度O(mn)空间复杂度O(1)注意事项必须先处理除第一行第一列外的元素最后再处理第一行和第一列如果一开始就清零第一行或第一列会破坏标记信息总结对比解法空间复杂度特点复制矩阵O(mn)最直观但不符合题目要求标记数组O(mn)简单改进但非最优第一行第一列标记O(1)最优解面试首选这道题的核心在于如何用有限的额外空间记录行和列的清零信息。从 O(mn) 到 O(mn) 再到 O(1)每一步优化都体现了空间换时间的思想转变值得细细品味。