73 矩阵置零

题目描述#

给定一个 m x n 的矩阵，如果某个位置的元素为 0，就把它所在的整行和整列都改成 0。

这题的限制在于要使用原地算法，也就是说不能再开一个同样大小的新矩阵来保存答案，必须直接在原矩阵上修改。

知识边界#

这题真正容易卡住的地方是“原地”要求。用两个布尔数组记录哪些行、哪些列要清零，做起来并不难，但空间复杂度是 O(m+n)，还不算最优。

更关键的点是理解第二种做法：把“这一行要不要清零”和“这一列要不要清零”直接存进第一列和第一行里。这样可以把额外空间压到 O(1)，但也会带来一个新问题，就是第一行和第一列本身是否原来就有 0。所以还要额外记录 firstRowHasZero 和 firstColHasZero，避免最后把标记和原始数据混在一起。

另外，这份代码用了 slices.Contains 和 clear。如果 Go 版本较旧，就需要自己补对应逻辑。

解法一：额外记录行和列#

第一种写法最直接。先遍历整个矩阵，如果 matrix[i][j] == 0，就把第 i 行和第 j 列分别记下来。等扫描结束后，再做第二次遍历：只要当前位置所在的行或列被标记过，就把它置为 0。

这种方法的优点是思路非常顺，不容易出错。因为第一轮只负责“记录”，第二轮只负责“修改”，不会出现刚改成 0 又影响后续判断的问题。

它的时间复杂度是 O(mn)，因为矩阵总共扫了两遍；额外空间复杂度是 O(m+n)，来自两个布尔数组。这也是它相对题目要求稍弱的地方。

代码#

func setZeroes(matrix [][]int) {
	m, n := len(matrix), len(matrix[0])
	rowHaszero := make([]bool, m)
	cowHaszero := make([]bool, n)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == 0 {
				rowHaszero[i] = true
				cowHaszero[j] = true
			}
		}
	}
	for i, rz := range rowHaszero {
		for j, cz := range cowHaszero {
			if rz == true || cz == true {
				matrix[i][j] = 0
			}
		}
	}
}

解法二：把标记压到第一行和第一列#

第二种写法是在第一种思路上的继续优化。既然我们只是想知道“某一行以后要不要变成 0”“某一列以后要不要变成 0”，那这些标记不一定非要放在额外数组里，也可以直接放到矩阵自身。

具体做法是：

用第一列的 matrix[i][0] 表示第 i 行是否需要清零
用第一行的 matrix[0][j] 表示第 j 列是否需要清零

但第一行和第一列本身也可能原来就有 0，所以要先单独记录两个状态：

firstRowHasZero 表示第一行最开始是否包含 0
firstColHasZero 表示第一列最开始是否包含 0

接着从 (1,1) 开始遍历矩阵。如果某个位置是 0，就把这一行对应的第一列位置和这一列对应的第一行位置都设成 0，相当于打上标记。等所有标记打完后，再从 (1,1) 开始第二次遍历：只要当前行标记或列标记为 0，就把当前位置设为 0。最后根据前面保存的两个布尔值，再决定要不要把整条第一行、第一列清零。

这样做之后，时间复杂度仍然是 O(mn)，但额外空间复杂度降到了 O(1)，这才是题目要求的原地做法。

代码#

func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])

    // 记录第一行是否包含 0
    firstRowHasZero := slices.Contains(matrix[0], 0)

    // 记录第一列是否包含 0
    firstColHasZero := false
    for _, row := range matrix {
        if row[0] == 0 {
            firstColHasZero = true
            break
        }
    }

    // 用第一列 matrix[i][0] 保存 rowHasZero[i]
    // 用第一行 matrix[0][j] 保存 colHasZero[j]
    for i := 1; i < m; i++ { // 无需遍历第一行，如果 matrix[0][j] 本身是 0，那么相当于 colHasZero[j] 已经是 true
        for j := 1; j < n; j++ { // 无需遍历第一列，如果 matrix[i][0] 本身是 0，那么相当于 rowHasZero[i] 已经是 true
            if matrix[i][j] == 0 {
                matrix[i][0] = 0 // 相当于 rowHasZero[i] = true
                matrix[0][j] = 0 // 相当于 colHasZero[j] = true
            }
        }
    }

    for i := 1; i < m; i++ { // 跳过第一行，留到最后修改
        for j := 1; j < n; j++ { // 跳过第一列，留到最后修改
            if matrix[i][0] == 0 || matrix[0][j] == 0 { // i 行或 j 列有 0
                matrix[i][j] = 0
            }
        }
    }

    // 如果第一列一开始就包含 0，那么把第一列全变成 0
    if firstColHasZero {
        for _, row := range matrix {
            row[0] = 0
        }
    }

    // 如果第一行一开始就包含 0，那么把第一行全变成 0
    if firstRowHasZero {
        clear(matrix[0])
    }
}

第二种代码来自灵茶山艾府的题解思路整理，原链接如下：

73. 矩阵置零 - 一步步优化，从 O(m+n) 到 O(1) 空间