給定一個 m x n 的矩陣，如果某個元素為 0，則將其所在的整行和整列都設為 0。要求原地操作。
Example:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]
Intuition
TIP
核心思路：用矩陣的第一行和第一列作為標記，記錄哪些行列需要歸零，達到 O(1) 額外空間。
- 不能邊遍歷邊歸零，否則新產生的 0 會造成連鎖反應
- 需要先記錄哪些行列有 0，再統一歸零
- 用額外的 Set 記錄需要 O(m + n) 空間；用矩陣自身的第一行/列當標記只需 O(1)
Approaches
1. Track with Set — O(m * n) / O(m + n)
- Idea: 先遍歷矩陣找出所有 0 的行列，存入兩個 Set，再遍歷矩陣歸零
- Time:
O(m * n)- 遍歷矩陣兩次 - Space:
O(m + n)- 兩個 Set 記錄行列
class Solution {
fun setZeroes(matrix: Array<IntArray>) {
val rows = HashSet<Int>()
val cols = HashSet<Int>()
val m = matrix.size
val n = matrix[0].size
for (i in 0 until m) {
for (j in 0 until n) {
if (matrix[i][j] == 0) {
rows.add(i)
cols.add(j)
}
}
}
for (i in 0 until m) {
for (j in 0 until n) {
if (i in rows || j in cols) {
matrix[i][j] = 0
}
}
}
}
}⭐ 2. Use First Row/Col as Markers — O(m * n) / O(1)
- Idea: 用第一行和第一列記錄該列/行是否需要歸零，額外用一個變數記錄第一列本身是否需要歸零
- Time:
O(m * n)- 遍歷矩陣兩次 - Space:
O(1)- 只用一個額外變數
class Solution {
fun setZeroes(matrix: Array<IntArray>) {
val m = matrix.size
val n = matrix[0].size
var firstColZero = false
for (i in 0 until m) {
if (matrix[i][0] == 0) firstColZero = true
for (j in 1 until n) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
// 從下往上歸零（避免先改到第一行/列的標記）
for (i in m - 1 downTo 0) {
for (j in n - 1 downTo 1) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0
}
}
if (firstColZero) matrix[i][0] = 0
}
}
}WARNING
歸零時必須從最後一行開始往上處理，因為第一行的標記值在處理其他行時還需要使用。如果先處理第一行，標記會被破壞。
🔑 Takeaways
- Pattern: 利用矩陣自身空間做標記是常見的 O(1) 空間優化技巧
- Key trick: 用第一行/列當標記時，處理順序很重要——必須最後才處理用來當標記的那行/列