算法73. 矩阵置零-EW帮帮网

给定一个 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]:
            return
        
        m,n=len(matrix),len(matrix[0])

        # 1. 检查第一行/第一列是否原本就有0
        first_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] = 0
                    matrix[0][j] = 0
        
        # 3. 根据标记，把中间部分（非第一行/列）置零
        for i in range(1,m):
            if matrix[i][0] == 0:
                # 找到要置零的行，全部置零
                for j in range(1,n):
                    matrix[i][j] = 0
        
        for 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] = 0

        if 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：

matrix[1][2] == 0 → 第1行第2列是0
- matrix[1][0] = 0 → 标记第1行要清零
- matrix[0][2] = 0 → 标记第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] = 0

if 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) 空间解法的精髓：用矩阵自己当哈希表

算法73. 矩阵置零

解法：