矩阵置零:先插旗,再统一清
扫到 0 不能立刻改整行整列。把「这一行/列稍后要清」记在第 0 行和第 0 列,两趟扫描,额外只花两个布尔。
第一趟:matrix[i][0] 与 matrix[0][j] 置 0 标记含零行列;第二趟据此清零,最后单独处理第 0 行/列是否真含零。时间 O(m·n),空间 O(1)。
给一个 m×n 矩阵,如果某个位置是 0,就把它所在的整行和整列都变成 0。题目希望尽量原地做:不要再复制一整块和原矩阵一样大的内存。
主例是 3×3:第一行 1 1 1,第二行 1 0 1,第三行 1 1 1。唯一的 0 在 (1,1)。第 1 行、第 1 列被株连,四个角落的 1 幸存,因为它们既不在第 1 行,也不在第 1 列。输出是 1 0 1 / 0 0 0 / 1 0 1。
扫到 0 立刻改,会分不清「本来就是 0」和「刚被株连出来的 0」。本文要回答:旗子为什么能挤进第 0 行和第 0 列,以及交汇点 matrix[0][0] 为什么必须拆成两个布尔。
先标记含零行列,再按旗清内部
错的路是扫到 0 立刻把这一行这一列改成 0。主例里你先清第 1 行,matrix[1][0] 从 1 变成 0。继续扫到这个新 0,又会把第 0 列整列清掉,四个角也被误杀。一边读一边写,读到的已经不是原图。
贵的路是先完整复制一份。只在原矩阵上读 0,只在副本上写 0。主例能做对,空间是整整一块 m×n。折中一点:开 row[m]、col[n] 两个一维数组记旗子,第一遍只做标记,第二遍按标记清零,空间掉到 O(m+n)。原地做法不过是再问一句:这两段旗子能不能挤进矩阵自己的第一行、第一列?能,因为它们本来就是可以按下标跳转的数组。
顺序必须拆开。先用两个布尔记下「第 0 行本来有没有 0」「第 0 列本来有没有 0」,否则后面往行首列首插旗时,分不清那是原装 0 还是标记。然后只扫内部格子(i≥1,j≥1):谁是 0,就在 matrix[i][0] 和 matrix[0][j] 写 0。旗子全部插完,再统一看内部:行首或列首是 0,就把自己清零。第 0 行、第 0 列最后才按那两个布尔整段清——它们还在给别人当旗,提前清掉旗就丢了。
matrix[0][0] 身兼第一行旗和第一列旗,必须拆开。你分不清它是 0 到底表示「第 0 列被内部株连」还是「第 0 行本来就要整行清零」。两个布尔就是把这一格的双重身份拆开。
用手走主例。第 0 行、第 0 列都没有原装 0,firstRow=false,firstCol=false。再扫内部,只有 (1,1) 是 0,于是插旗:matrix[1][0]=0,matrix[0][1]=0。矩阵此刻变成 1 0 1 / 0 0 1 / 1 1 1。右下角的 1 还在,株连还没执行,演示场景第一帧标出的正是「第 1 行、第 1 列要清」。
第二趟只处理内部。(1,1) 行首是 0,保持 0;(1,2) 行首是 0,清成 0;(2,1) 列首是 0,清成 0;(2,2) 行首列首都是 1,保持 1。内部做完已经是 1 0 1 / 0 0 0 / 1 0 1。两个布尔都是 false,第 0 行第 0 列不用整段清。第 0 行那个 0 是旗子,恰好也是「第 1 列被株连」之后该留下的值。
若原矩阵第一行自己就有 0,必须靠 firstRow 这面独立旗。否则你可能把内部还没轮到的 1 提前清掉,也可能先清第 0 行把另一面列旗擦掉。旗子必须先全部插完,再统一清内部,最后才动第 0 行第 0 列。
内嵌标记row[m]、col[n] 两段旗子被挤进第 0 行和第 0 列,额外只留两个布尔拆开交汇点。这能成立,是因为下标可以 O(1) 跳去行首、列首。边读边写会把株连出来的 0 当成原装 0。
Go:首行首列当标记
func setZeroes(matrix [][]int) {m, n := len(matrix), len(matrix[0])firstRow, firstCol := false, falsefor j := 0; j < n; j++ { if matrix[0][j] == 0 { firstRow = true } }for i := 0; i < m; i++ { if matrix[i][0] == 0 { firstCol = true } }for i := 1; i < m; i++ {for j := 1; j < n; j++ {if matrix[i][j] == 0 {matrix[i][0] = 0matrix[0][j] = 0}}}for i := 1; i < m; i++ {for j := 1; j < n; j++ {if matrix[i][0] == 0 || matrix[0][j] == 0 {matrix[i][j] = 0}}}if firstRow { for j := 0; j < n; j++ { matrix[0][j] = 0 } }if firstCol { for i := 0; i < m; i++ { matrix[i][0] = 0 } }}
1先扫第 0 行、第 0 列,把「本来有没有 0」记进 firstRow、firstCol。主例两面都是 false。
2再扫内部:谁是 0,就在行首、列首插旗。主例只在 (1,1) 插下第 1 行和第 1 列。
3第二趟只看内部的行首或列首。旗在,就把自己清零。四个角既不在第 1 行也不在第 1 列,留下 1。
4最后才按两个布尔整段清第 0 行、第 0 列。它们一直在当旗,不能提前清。
总结
内部 0 在行首列首插旗,第二趟按旗清内部;第 0 行第 0 列最后按预先记下的布尔清。
- 扫到 0 立刻改整行整列,会把株连出来的 0 当成原装 0,四个角会被误杀。
- 第 0 行、第 0 列就是 row[]、col[] 两段旗子。matrix[0][0] 身兼两职,必须拆成 firstRow、firstCol。
- 旗插完再清内部,最后才动第 0 行第 0 列。主例输出 1 0 1 / 0 0 0 / 1 0 1。