給定一個 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) 空間解法的精髓：用矩陣自己當哈希表

---