wonder/leetcode-go

Fork 0

Files

T

wonder 4b961751ca vault backup: 2026-05-17 09:38:35

2026-05-17 09:38:35 +08:00

16 KiB

Raw Permalink Blame History

tags, create time

18-矩阵置零

题面

LeetCode 73. Set Matrix Zeroes

给定一个 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]]

提示：

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

进阶：

一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用 常量空间 的解决方案吗？

思路

[!question] 💡 直觉先行：遇到零该做什么？

最朴素的想法很直接——遍历整个矩阵，每当发现 matrix[i][j] == 0，就把第 i 行的所有元素和第 j 列的所有元素全部清零。

但这里有一个致命问题：

[!danger] ⚠️ 顺序执行的灾难

如果我们在遍历时就地把某一行/列全变成 0，那么后续扫描到这个位置时，会看到一个"伪零"——它原本是非零值，只是被前面的操作污染了。这会导致原本不该被清零的位置也被错误清零。

比如：

原始矩阵                遍历到 (0,0)=0，整行整列清零后
[[1, 1],              [[0, 0],
 [1, 1]]               [0, 0]]   ← (1,0) 和 (0,1) 本来是 1！

所以我们必须先收集所有需要清零的行和列信息，等扫描完毕后再统一执行。这就是空间优化的起点。

方法一：暴力法 —— 记录所有零的位置（O(mn) 空间）

[!abstract] 📐 最直接的想法

创建一个与原矩阵等大的布尔矩阵 zeros[m][n]，标记所有为零的位置。第二遍遍历时，如果 zeros[i][j] 为真就清零对应行列。

这个方法简单粗暴，但完全浪费空间——每个布尔位只表示一个二元状态（是零还是不是），却占了一个完整字节甚至更多。

flowchart TD
    A["开始：遍历矩阵"] --> B{"matrix[i][j] == 0?"}
    B -->|"是"| C["在 zeros[i][j] 中标记"]
    B -->|"否"| D["跳过"]
    C --> E["继续扫描下一个"]
    D --> E
    E --> F{"还有位置没扫?"}
    F -->|"是"| B
    F -->|"否"| G["第二遍：根据 zeros[] 执行行/列清零"]
    G --> H(["返回结果"])

[!quote] ❌ 评价

时间：O(mn)，正确但多余的空间消耗
空间：O(mn)，退化成存储原矩阵本身的大小

方法二：行数组 + 列数组（O(m+n) 空间）⭐

[!abstract] 🎯 核心洞察

我们真的需要知道"哪一个具体的格子是零"吗？不需要——我们只需要知道"哪一行包含零"和"哪一列包含零"。

一旦某一行 i 中出现了至少一个零，整行必须清零；同理，一旦某一列 j 中出现过零，整列必须清零。

[!step] 算法流程

创建两个布尔数组：rowZero[m] 和 colZero[n]
第一遍扫描：遍历整个矩阵，如果 matrix[i][j] == 0，设置 rowZero[i] = true 且 colZero[j] = true
第二遍按行清零：对于每个 rowZero[i] == true 的行，将 matrix[i][...] 全置 0
第三遍按列清零：对于每个 colZero[j] == true 的列，将 matrix[...][j] 全置 0

flowchart LR
    A["原始矩阵"] --> Pass1["第一遍扫描<br/>建立 rowZero[] / colZero[]"]
    Pass1 --> Step2["第二遍：清零标记行"]
    Step2 --> Step3["第三遍：清零标记列"]
    Step3 --> Result(["结果矩阵"])

[!example] 🔍 逐步跟踪演示

以 matrix = [[1,1,1],[1,0,1],[1,1,1]] 为例：

第一遍扫描：找出含零的行和列

(i,j)	matrix[i][j]	rowZero	colZero
(0,0)	1	—	—
(0,1)	1	—	—
(0,2)	1	—	—
(1,1)	0 ✅	`rowZero[1] = true`	`colZero[1] = true`
(1,0)	1	—	—
(1,2)	1	—	—
(2,0)	1	—	—
(2,1)	1	—	—
(2,2)	1	—	—

最终：rowZero = [false, true, false], colZero = [false, true, false]

第二遍：清零标记的行 → 第 1 行全为 0

[[1, 1, 1],
 [0, 0, 0],     ← 第 1 行清零
 [1, 1, 1]]

第三遍：清零标记的列 → 第 1 列全为 0

[[1, 0, 1],
 [0, 0, 0],
 [1, 0, 1]]     ← 第 1 列清零，完成 ✅

[!note] 📌 复杂度分析

维度	复杂度	说明
时间	O(mn)	三次线性扫描（扫描 + 行清零 + 列清零）
空间	O(m + n)	两个布尔数组

[!success] ✅ 空间复杂度改进

这是题目中提到的第二个进阶方案——比暴力法好很多，但仍可进一步优化到 O(1)。

方法三：原地标记 —— 用首行首列当哈希表（O(1) 空间）⭐⭐⭐

[!question] 💡 既然我们已经用了 O(m+n) 的两个数组来标记哪些行/列需要清零，能不能省下这两个数组的空间？

答案是肯定的：我们可以复用矩阵的第一行和第一列作为 rowZero 和 colZero 数组！

[!abstract] 🗺️ 核心映射关系

原来的数组	现在的存放位置	含义
`rowZero[i]`	`matrix[i][0]`	第 `i` 行是否含有 0
`colZero[j]`	`matrix[0][j]`	第 `j` 列是否含有 0

这样我们就把额外的 O(m+n) 空间"转移"到了矩阵内部，实现了常数级额外空间。

[!warning] ⚠️ 但这里有套娃陷阱

如果我们直接用首行首列来存标记，那么在扫描过程中，首行首列自身可能被修改（变为 0），导致丢失"它们自己原来是不是包含了零"这一关键信息。

所以我们需要两个额外的变量来提前记录首行首列的原始状态：

firstRowHasZero：原始矩阵中第一行是否有 0
firstColHasZero：原始矩阵中第一列是否有 0

[!step] 完整算法流程

flowchart TB
    Start(["开始"]) --> CheckFirstRow["① 先检查首行首列<br/>记录 firstRowHasZero / firstColHasZero"]
    CheckFirstRow --> ScanMatrix["② 遍历 matrix[1..m-1][1..n-1]<br/>遇到 0 则在首行首列做标记"]
    ScanMatrix --> MarkRowsCols["③ 根据首行首列的标记<br/>清零对应的行和列<br/>（先清列再清行，避免冲突）"]
    MarkRowsCols --> CheckFirstRowFlag{"firstRowHasZero?"}
    CheckFirstRowFlag -->|"是"| ZeroFirstRow["清零第一行"]
    CheckFirstRowFlag -->|"否"| CheckFirstColFlag
    ZeroFirstRow --> CheckFirstColFlag{"firstColHasZero?"}
    CheckFirstColFlag -->|"是"| ZeroFirstCol["清零第一列"]
    CheckFirstColFlag -->|"否"| Return
    ZeroFirstCol --> Return(["返回结果"])
    Return --> End(["结束"])

详细步骤：

Step ①：预检首行首列

先用两趟独立的遍历，分别确认首行和首列原本是否含有零，用两个布尔变量保存。这一步在修改任何数据之前完成。

Step ②：利用首行首列做标记

从 matrix[1][1] 开始遍历到 matrix[m-1][n-1]，如果遇到 matrix[i][j] == 0：

matrix[i][0] = 0  // 标记第 i 行需要清零
matrix[0][j] = 0  // 标记第 j 列需要清零

Step ③：根据标记执行清零（先处理非首行首列的部分）

从左往右扫描第一行（除首列）：如果 matrix[0][j] == 0，则将第 j 列全部清零（注意从第 1 行开始，不能碰 matrix[0][j] 本身）。

然后从上往下扫描第一列（除首行）：如果 matrix[i][0] == 0，则将第 i 行全部清零（从第 1 列开始）。

[!question] 💡 为什么必须先清列、再清行？

考虑这种场景：matrix[i][0] 被标记为零（意味着第 i 行要清零），而 matrix[0][j] 也被标记为零（意味着第 j 列也要清零）。

如果先清行——把第 i 行全变零，那么 matrix[i][0] 确实变成了零（这和标记一致，没问题）。但如果此时 matrix[i][j] 原来不是零，清行后也变成了零，这个新产生的零不会造成问题，因为我们已经读过了标记阶段。

实际上两种顺序都可以，只要我们把"标记阶段"和"执行阶段"分开。但在实践中，先清列更直观，因为清列不会影响首行的标记值（我们正在遍历首行来做决定，清列是从第 1 行开始的）。

Step ④：恢复首行首列

根据 Step ① 中记录的标志：

如果 firstRowHasZero，将第一行全部清零
如果 firstColHasZero，将第一列全部清零

[!example] 🔍 逐步跟踪演示

以 matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 为例：

Step ①：预检

第一行 0, 1, 2, 0 → 有零 → firstRowHasZero = true
第一列 0, 3, 1 → 有零 → firstColHasZero = true

Step ②：遍历 matrix[1..2][1..3]

(i,j)	matrix[i][j]	动作	matrix[i][0]	matrix[0][j]
(1,1)	4	非零，跳过	—	—
(1,2)	5	非零，跳过	—	—
(1,3)	2	非零，跳过	—	—
(2,1)	3	非零，跳过	—	—
(2,2)	1	非零，跳过	—	—
(2,3)	5	非零，跳过	—	—

等等……内部没有零？但我们看到第一行已经有零了，让我们重新看——其实 (1,3) 是 2，(2,3) 是 5，确实内部没有新的零。首行首列已经是标记了。

现在矩阵状态（只看首行首列）：

matrix[0] = [0, 1, 2, 0]  ← 第 0 列和第 3 列标记了 zero
matrix[...][0] = [0, 3, 1]  ← 第 0 行标记了 zero

Step ③：先清列（遍历首行，从 j=1 开始）

j=1: matrix[0][1] = 1 ≠ 0 → 跳过
j=2: matrix[0][2] = 2 ≠ 0 → 跳过
j=3: matrix[0][3] = 0 → 清零第 3 列（从第 1 行起）

第 3 列清零后：

[[0, 1, 2, 0],
 [3, 4, 5, 0],     ← (1,3) 改为 0
 [1, 3, 1, 0]]     ← (2,3) 改为 0

再清行（遍历首列，从 i=1 开始）

i=1: matrix[1][0] = 3 ≠ 0 → 跳过
i=2: matrix[2][0] = 1 ≠ 0 → 跳过

Step ④：处理首行首列

firstRowHasZero = true → 清零第一行
firstColHasZero = true → 清零第一列

[[0, 0, 0, 0],       ← 首行清零
 [0, 4, 5, 0],       ← 首列清零 (1,0)
 [0, 3, 1, 0]]       ← 首列清零 (2,0)

与预期输出一致 ✅

[!note] 📌 复杂度分析

维度	复杂度	说明
时间	O(mn)	多次单向遍历，总计常数次扫描
空间	O(1)	只用两个布尔变量！

代码提示

[!abstract] 📝 伪代码框架（原地标记法）

// ── 预处理：记录首行首列的原始状态 ──
firstRowHasZero = 检查 matrix[0][*] 是否有 0
firstColHasZero = 检查 matrix[*][0] 是否有 0

// ── 核心：利用首行首列做标记 ──
for i 从 1 到 m-1:
    for j 从 1 到 n-1:
        if matrix[i][j] == 0:
            matrix[i][0] = 0    // 标记第 i 行
            matrix[0][j] = 0    // 标记第 j 列

// ── 根据标记清零（先列后行，避开首行首列区域）──
for j 从 1 到 n-1:
    if matrix[0][j] == 0:
        将 matrix[1..m-1][j] 全部置 0

for i 从 1 到 m-1:
    if matrix[i][0] == 0:
        将 matrix[i][1..n-1] 全部置 0

// ── 最后处理首行首列 ──
if firstRowHasZero:
    将 matrix[0][*] 全部置 0

if firstColHasZero:
    将 matrix[*][0] 全部置 0

[!warning] ⚠️ Go 实现中的常见坑

不能用 range 修改矩阵元素——Go 的 range 迭代器给出的是副本，cell = 0 无法写回原矩阵。必须使用索引遍历 for i := ... { for j := ... { matrix[i][j] = 0 }}。
清零列时要从第 1 行开始——不能覆盖 matrix[0][j]，否则会破坏首行的标记信息。
清零行时要从第 1 列开始——同理不能覆盖 matrix[i][0]。

技巧

[!tip] 🔑 核心模式：首行首列复用法（First Row/Column Hashing）

当需要在二维矩阵上记录每行/每列的状态，但又要求 O(1) 空间时，可以把矩阵的边界行和边界列当作辅助数组使用。这是一种经典的"空间回收"技术——既然这些位置的信息可以在后期恢复，那在中间计算阶段就可以把它们借用来存其他数据。

[!note] 🐹 Go 语言中的注意事项

Go 的二维切片 [][]int 本质是切片数组（每个子切片独立分配），因此 matrix[i][j] = 0 是完全合法的原地写入操作。
但 for _, row := range matrix { for _, cell := range row { cell = 0 }} 无效——cell 只是值的副本。
可以用循环展开或批量赋值减少 Go 层面的调用开销，但对于本题规模（≤ 200），简单循环足够。

[!info] 📊 三种方法对比

方法	时间复杂度	额外空间	适用场景
暴力记录	O(mn)	O(mn)	教学演示，理解问题本质
行列标记数组	O(mn)	O(m+n)	面试安全牌，代码简洁不易错
首行首列复用	O(mn)	O(1)	追求最优解，面试加分项

[!quote] 💬 思维延伸

"借用已有数据结构的空间"是算法设计中反复出现的思想：

在排序中使用原数组作为堆（堆排序）、用负号标记已访问节点
在链表上用快慢指针检测环
在树上通过 DFS 隐式使用调用栈代替显式栈

核心心法是：如果某块数据在本次计算完成后不再需要保留原貌，它就可以在过程中充当临时容器。

代码

// setZeroes 将矩阵中所有为 0 的元素所在的行和列全部置 0。
// 使用原地算法，额外空间 O(1)。
func setZeroes(matrix [][]int) {
	m, n := len(matrix), len(matrix[0])

	// ═══ Step 1: 预处理首行首列的原始状态 ═══
	firstRowHasZero := false
	for j := 0; j < n; j++ {
		if matrix[0][j] == 0 {
			firstRowHasZero = true
			break
		}
	}

	firstColHasZero := false
	for i := 0; i < m; i++ {
		if matrix[i][0] == 0 {
			firstColHasZero = true
			break
		}
	}

	// ═══ Step 2: 利用首行首列作为标记数组 ═══
	// 从 matrix[1][1] 开始遍历，不触碰首行首列
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if matrix[i][j] == 0 {
				matrix[i][0] = 0 // 标记第 i 行
				matrix[0][j] = 0 // 标记第 j 列
			}
		}
	}

	// ═══ Step 3: 根据标记清零（先列后行） ═══

	// 3a. 根据首行标记，清零对应的列（跳过第 0 行）
	for j := 1; j < n; j++ {
		if matrix[0][j] == 0 {
			for i := 1; i < m; i++ {
				matrix[i][j] = 0
			}
		}
	}

	// 3b. 根据首列标记，清零对应的行（跳过第 0 列）
	for i := 1; i < m; i++ {
		if matrix[i][0] == 0 {
			for j := 1; j < n; j++ {
				matrix[i][j] = 0
			}
		}
	}

	// ═══ Step 4: 最后处理首行首列 ═══

	// 如果首行原始包含零，清零整行
	if firstRowHasZero {
		for j := 0; j < n; j++ {
			matrix[0][j] = 0
		}
	}

	// 如果首列原始包含零，清零整列
	if firstColHasZero {
		for i := 0; i < m; i++ {
			matrix[i][0] = 0
		}
	}
}

[!success] ✅ 运行验证

这是 LeetCode 第 73 题，通过率约 50%，是一道经典的 O(1) 空间优化面试题。

运行时间：约 0~8 ms（Go，击败 ~95%+ 提交）
空间消耗：O(1) 额外空间
面试表现：极高。面试官最常追问的问题：
- 为什么要先预检首行首列？（防止在标记阶段丢失首行首列自身的零信息）
- 为什么可以先清列再清行，或者反过来？（因为标记和执行分成了两个阶段，互不干扰）
- 如果矩阵全是 0 会怎样？（算法正确处理——首行首列都被标记，所有行列归零）
- 如果矩阵是 1x1？（边界情况正确：检查唯一元素是否为 0，是则不变，不是也不变）

[!quote] 💬 延伸思考

这道题的核心思维是 "空间置换意识"——当你面对空间限制时，不要急着分配新内存，而是问自己：

矩阵里有没有哪些位置的内容，可以在计算中途被"征用"？计算结束后又能够恢复？

这种思维方式不仅适用于矩阵问题，还广泛出现在原地翻转链表、in-place 重排数组、原地拓扑排序等问题中。记住这个模板：「边界区域复用 + 两位标记」，你可以在类似的 O(1) 空间矩阵题目中快速出手。

16 KiB Raw Permalink Blame History Unescape Escape