題目描述:若矩陣中某個元素為 0,將其所在的整行整列設為 0,原地操作。
解題思路:O(1) 空間解法:用矩陣的第一行和第一列作為標記(記錄哪些行/列需要清零),但需要先用兩個布林變數記錄第一行和第一列本身是否含 0。第一步掃描標記,第二步根據標記清零(從後往前處理以避免覆蓋標記),第三步根據最初記錄清零第一行/列。
時間複雜度:O(m × n) — 常數次掃描整個矩陣。
空間複雜度:O(1) — 只用兩個額外布林變數。
1. Check if first row and first col contain any zero (save as flags) 2. For rows [1..m-1], cols [1..n-1]: if matrix[i][j]==0, mark matrix[i][0]=matrix[0][j]=0 3. Zero out rows and cols based on markers in first row/col 4. Apply saved flags to first row and first col
額外集合追蹤 O(m+n) 空間:記錄含 0 的行列,再掃描一次清空 — 空間效率差。
嵌套迴圈標記 O(1) 空間但 O(mn) 時間:掃描每個 0,再掃描該行列重複設置 — 時間複雜度更差。