算法73. 矩阵置零

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

解法：

class Solution:def setZeroes(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""if not matrix or not matrix[0]:returnm,n=len(matrix),len(matrix[0])# 1. 检查第一行/第一列是否原本就有0first_row_has_zero = any(matrix[0][j]==0 for j in range(n))first_col_has_zero = any(matrix[i][0]==0 for i in range(m))# 2. 用第一行和第一列作为“标记数组”# 也就是把要置为0的行列标记出来for i in range(1,m):for j in range(1,n):if matrix[i][j]==0:matrix[i][0] = 0matrix[0][j] = 0# 3. 根据标记，把中间部分（非第一行/列）置零for i in range(1,m):if matrix[i][0] == 0:# 找到要置零的行，全部置零for j in range(1,n):matrix[i][j] = 0for j in range(1,n):if matrix[0][j] == 0:for i in range(1,m):matrix[i][j] = 0# 4. 最后再处理第一行和第一列if first_row_has_zero:for j in range(n):matrix[0][j] = 0if first_col_has_zero:for i in range(m):matrix[i][0] = 0 

使用5x5的矩阵来完整演示这个算法的每一步执行过程如下：

---

📌 示例矩阵：

原始矩阵：
[[ 1,  2,  3,  4,  5],[ 6,  7,  0,  8,  9],[10, 11, 12, 13, 14],[15,  0, 16, 17, 18],[19, 20, 21, 22, 23]
]

目标：如果某个元素是 0，就把它所在的整行和整列都设为 0。

我们使用 O(1) 空间优化算法（用第一行/列做标记）。

---

✅ 步骤 1：判断第一行和第一列是否原本有 0

first_row_has_zero = any(matrix[0][j] == 0 for j in range(5))   → False
first_col_has_zero = any(matrix[i][0] == 0 for i in range(5))   → False

第一行：[1,2,3,4,5] → 没有 0
第一列：[1,6,10,15,19] → 没有 0

✅ 所以最后我们不会主动清零第一行和第一列，除非标记需要。

---

✅ 步骤 2：用第一行和第一列作为“标记位”

我们从 (1,1) 开始扫描（跳过第一行和第一列），发现 0 就在 matrix[i][0] 和 matrix[0][j] 打标记。

for i in range(1, 5):for j in range(1, 5):if matrix[i][j] == 0:matrix[i][0] = 0      # 标记第 i 行要清零matrix[0][j] = 0      # 标记第 j 列要清零

我们找到两个 0：

1. matrix[1][2] == 0 → 第1行第2列是0

   • matrix[1][0] = 0 → 标记第1行要清零
   • matrix[0][2] = 0 → 标记第2列要清零

2. matrix[3][1] == 0 → 第3行第1列是0

   • matrix[3][0] = 0 → 标记第3行要清零
   • matrix[0][1] = 0 → 标记第1列要清零

👉 打完标记后，矩阵变成：

[[ 1,  0,  0,  4,  5],   ← matrix[0][1]=0（第1列要清零），matrix[0][2]=0（第2列要清零）[ 0,  7,  0,  8,  9],   ← matrix[1][0]=0（第1行要清零）[10, 11, 12, 13, 14],[ 0,  0, 16, 17, 18],   ← matrix[3][0]=0（第3行要清零）[19, 20, 21, 22, 23]
]

🔔 注意：我们故意修改了第一行和第一列，把它们当作“标记墙”。

---

✅ 步骤 3：根据标记清零“中间部分”（非第一行/列）

① 清零被标记的行（从第1行开始）

for i in range(1, 5):if matrix[i][0] == 0:   # 第 i 行被标记了for j in range(1, 5):  # 把 j ≥ 1 的列清零matrix[i][j] = 0

• i=1: matrix[1][0]==0 → 清零 matrix[1][1] 到 matrix[1][4]
• i=3: matrix[3][0]==0 → 清零 matrix[3][1] 到 matrix[3][4]

当前矩阵：

[[ 1,  0,  0,  4,  5],[ 0,  0,  0,  0,  0],   ← 第1行清零（除了 matrix[1][0] 已是0）[10, 11, 12, 13, 14],[ 0,  0,  0,  0,  0],   ← 第3行清零[19, 20, 21, 22, 23]
]

---

② 清零被标记的列（从第1列开始）

for j in range(1, 5):if matrix[0][j] == 0:   # 第 j 列被标记了for i in range(1, 5):  # 把 i ≥ 1 的行清零matrix[i][j] = 0

• j=1: matrix[0][1]==0 → 清零第1列（i=1 到 4）
• j=2: matrix[0][2]==0 → 清零第2列（i=1 到 4）

注意：matrix[1][1], [1][2], [3][1], [3][2] 已是 0，但其他也要清：

• 第1列：matrix[2][1], matrix[4][1] → 设为 0
• 第2列：matrix[2][2], matrix[4][2] → 设为 0

当前矩阵：

[[ 1,  0,  0,  4,  5],[ 0,  0,  0,  0,  0],[10,  0,  0, 13, 14],   ← matrix[2][1] 和 [2][2] 被清零[ 0,  0,  0,  0,  0],[19,  0,  0, 22, 23]    ← matrix[4][1] 和 [4][2] 被清零
]

---

✅ 步骤 4：最后处理第一行和第一列

if first_row_has_zero:   → False → 不清零第一行for j in range(5): matrix[0][j] = 0if first_col_has_zero:   → False → 不清零第一列for i in range(5): matrix[i][0] = 0

所以第一行和第一列保持原样。

---

✅ 最终结果：

[[ 1,  0,  0,  4,  5],[ 0,  0,  0,  0,  0],[10,  0,  0, 13, 14],[ 0,  0,  0,  0,  0],[19,  0,  0, 22, 23]
]

---

✅ 验证是否正确？

原始 0 的位置：

• (1,2) → 第1行、第2列 → 应清零 → ✅
• (3,1) → 第3行、第1列 → 应清零 → ✅

结果：

• 第1行全0 → ✅
• 第3行全0 → ✅
• 第1列：matrix[i][1] 全为0（i≥1）→ ✅
• 第2列：matrix[i][2] 全为0（i≥1）→ ✅
• 第一行和第一列未被误清 → ✅

---

✅ 总结：算法全过程

步骤	操作	目的
1	检查第一行/列是否有 0	保存原始信息
2	扫描内部，用 matrix[i][0] 和 matrix[0][j] 打标记	空间复用，O(1)
3	根据 matrix[i][0]==0 清零行	读标记，清零中间行
4	根据 matrix[0][j]==0 清零列	读标记，清零中间列
5	最后根据 first_row/col_has_zero 清零第一行/列	保证完整性

---

💡 关键点回顾

• matrix[i][0] == 0 确实是被前面改过的，但这是设计好的标记机制
• 我们不是在“错误地读修改后的值”，而是在“正确地读标记”
• 这就是 O(1) 空间解法的精髓：用矩阵自己当哈希表

---