476 lines
16 KiB
Markdown
476 lines
16 KiB
Markdown
---
|
||
tags: ["LeetCode", "矩阵", "中等"]
|
||
create time: 2026-05-16 14:30
|
||
---
|
||
|
||
# 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]` 为真就清零对应行列。
|
||
|
||
这个方法简单粗暴，但完全浪费空间——每个布尔位只表示一个二元状态（是零还是不是），却占了一个完整字节甚至更多。
|
||
|
||
```mermaid
|
||
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] 算法流程
|
||
|
||
1. 创建两个布尔数组：`rowZero[m]` 和 `colZero[n]`
|
||
2. **第一遍扫描**：遍历整个矩阵，如果 `matrix[i][j] == 0`，设置 `rowZero[i] = true` 且 `colZero[j] = true`
|
||
3. **第二遍按行清零**：对于每个 `rowZero[i] == true` 的行，将 `matrix[i][...]` 全置 0
|
||
4. **第三遍按列清零**：对于每个 `colZero[j] == true` 的列，将 `matrix[...][j]` 全置 0
|
||
|
||
```mermaid
|
||
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] 完整算法流程
|
||
|
||
```mermaid
|
||
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`：
|
||
|
||
```go
|
||
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 实现中的常见坑
|
||
|
||
1. **不能用 `range` 修改矩阵元素**——Go 的 `range` 迭代器给出的是副本，`cell = 0` 无法写回原矩阵。必须使用索引遍历 `for i := ... { for j := ... { matrix[i][j] = 0 }}`。
|
||
2. **清零列时要从第 1 行开始**——不能覆盖 `matrix[0][j]`，否则会破坏首行的标记信息。
|
||
3. **清零行时要从第 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 隐式使用调用栈代替显式栈
|
||
|
||
核心心法是：**如果某块数据在本次计算完成后不再需要保留原貌，它就可以在过程中充当临时容器。**
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
// 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) 空间矩阵题目中快速出手。
|