矩阵置零

怎样从“矩阵 [[1,1,1],[1,0,1],[1,1,1]],把含 0 的行列置 0。”推导出 矩阵模拟 · 置零，并证明每次状态变化都不会漏掉答案？

中心结论：先标记后清零：用第一行/第一列当 O(1) 公告栏，firstRowZero/firstColZero 保存边界原始状态，最后处理首行首列。

给定一个 `m x n` 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

在本站主例中，矩阵 [[1,1,1],[1,0,1],[1,1,1]],把含 0 的行列置 0。

算法最终需要得到或观察：原始 0 所在行列全部封锁为 0，输出 [[1,0,1],[0,0,0],[1,0,1]]。

凭感觉逐格转向容易重复或漏掉边角；固定方向和边界收缩保证每个格子恰好处理一次。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“矩阵边界框”，明确答案需要观察什么。
2. 2状态只维护 firstRowZero、firstColZero、扫描 i/j、行/列标记。
3. 3转移每一步按照 先标记后清零：用第一行/第一列当 O(1) 公告栏，firstRowZero/firstColZero 保存边界原始状态，最后处理首行首列。
4. 4收尾读取 原始 0 所在行列全部封锁为 0，输出 [[1,0,1],[0,0,0],[1,0,1]]。，并复核边界与复杂度。

每走完一条边，只收紧刚刚完成的那一侧边界。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：firstRowZero、firstColZero、扫描 i/j、行/列标记。

此题考查对程序的控制能力，无算法思想。题目要求采用原地的算法，所有修改即在原二维数组上进行。在二维数组中有 2 个特殊位置，一个是第一行，一个是第一列。它们的特殊性在于，它们之间只要有一个 0，它们都会变为全 0 。先用 2 个变量记录这一行和这一列中是否有 0，防止之后的修改覆盖了这 2 个地方。然后除去这一行和这一列以外的部分判断是否有 0，如果有 0，将它们所在的行第一个元素标记为 0，所在列的第一个元素标记为 0 。最后通过标记，将对应的行列置 0 即可。

先标记后清零：用第一行/第一列当 O(1) 公告栏，firstRowZero/firstColZero 保存边界原始状态，最后处理首行首列。

执行过程中持续维护：firstRowZero、firstColZero、扫描 i/j、行/列标记。

正确性依赖以下不变量：matrix[i][0]==0 表示第 i 行最终需要清零。；matrix[0][j]==0 表示第 j 列最终需要清零。；第一行第一列必须最后处理，因为它们承担标记存储。

面试时可以压缩为：用首行首列当 O(1) 标记区：先保存边界原始 0 到 firstRowZero/firstColZero，扫描内部写标记，按标记清零内部，最后处理边界。O(mn) 时间 O(1) 空间。

落到当前题，执行机制可以压缩为：先标记后清零：用第一行/第一列当 O(1) 公告栏，firstRowZero/firstColZero 保存边界原始状态，最后处理首行首列。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入矩阵 [[1,1,1],[1,0,1],[1,1,1]],把含 0 的行列置 0。 因为：先标记后清零：用第一行/第一列当 O(1) 公告栏，firstRowZero/firstColZero 保存边界原始状态，最后处理首行首列。
2. 2首行首列作标记,避免额外 O(mn) 空间找所有 0 的位置。 因为：不能直接改否则丢失信息。
3. 3发现 0 于 (1,1),标记第 1 行与第 1 列标记行列。 因为：第二遍根据标记置零。
4. 4矩阵置零完成第二遍应用标记。 因为：O(mn) O(1) 额外空间。
5. 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6. 6收尾与复杂度原始 0 所在行列全部封锁为 0，输出 [[1,0,1],[0,0,0],[1,0,1]]。 因为：时间 O(mn) · 空间 O(1)。先标记后清零：用第一行/第一列当 O(1) 公告栏，firstRowZero/firstColZero 保存边界原始状态，最后处理首行首列。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func setZeroes(matrix [][]int) {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return
	}
	isFirstRowExistZero, isFirstColExistZero := false, false
	for i := 0; i < len(matrix); i++ {
		if matrix[i][0] == 0 {
			isFirstColExistZero = true
			break
		}
	}
	for j := 0; j < len(matrix[0]); j++ {
		if matrix[0][j] == 0 {
			isFirstRowExistZero = true
			break
		}
	}
	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[0]); j++ {
			if matrix[i][j] == 0 {
				matrix[i][0] = 0
				matrix[0][j] = 0
			}
		}
	}
	// 处理[1:]行全部置 0
	for i := 1; i < len(matrix); i++ {
		if matrix[i][0] == 0 {
			for j := 1; j < len(matrix[0]); j++ {
				matrix[i][j] = 0
			}
		}
	}
	// 处理[1:]列全部置 0
	for j := 1; j < len(matrix[0]); j++ {
		if matrix[0][j] == 0 {
			for i := 1; i < len(matrix); i++ {
				matrix[i][j] = 0
			}
		}
	}
	if isFirstRowExistZero {
		for j := 0; j < len(matrix[0]); j++ {
			matrix[0][j] = 0
		}
	}
	if isFirstColExistZero {
		for i := 0; i < len(matrix); i++ {
			matrix[i][0] = 0
		}
	}
}

func main() {
    // 1. 主例
    //    输入：mode="set-zeroes", matrix=[[1,1,1],[1,0,1],[1,1,1]]
    //    期望：原始 0 所在行列全部封锁为 0，输出 [[1,0,1],[0,0,0],[1,0,1]]。
    //
    // 2. 失败 / 未命中
    //    检查：边扫描边清零会把制造的 0 当成原始污染源。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC54 螺旋矩阵；LC240 搜索矩阵
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意矩阵 [[1,1,1],[1,0,1],[1,1,1]],把含 0 的行列置 0。
2. 2重复凭感觉逐格转向容易重复或漏掉边角；固定方向和边界收缩保证每个格子恰好处理一次。
3. 3优化先标记后清零：用第一行/第一列当 O(1) 公告栏，firstRowZero/firstColZero 保存边界原始状态，最后处理首行首列。
4. 4证明matrix[i][0]==0 表示第 i 行最终需要清零。；matrix[0][j]==0 表示第 j 列最终需要清零。；第一行第一列必须最后处理，因为它们承担标记存储。
5. 5复杂度时间 O(mn)，空间 O(1)