一、題目

??編寫一種算法，若M × N矩陣中某個(gè)元素為0，則將其所在的行與列清零。

??點(diǎn)擊此處跳轉(zhuǎn)題目。

示例 1：

輸入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
輸出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]

示例 2：

輸入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
輸出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

二、C# 題解

??此題有很多方法解，無外乎都是記錄需要清零的行與列，這種寫法太無聊了。這里提出一種遞歸的方式，只需要遍歷矩陣一次即可。當(dāng)遇到 0 時(shí)，使用 set0 變量記錄該位置，遍歷完成后，重置所有 set0。

public class Solution {public void SetZeroes(int[][] matrix) {BFS(ref matrix, 0, 0); // 廣度優(yōu)先遍歷}public void BFS(ref int[][] matrix, int i, int j) {int m = matrix.Length, n = matrix[0].Length;if (i == m && j == 0) return; // 遞歸出口// 計(jì)算下一個(gè)位置int next_i = i, next_j = j + 1;if (next_j == n) {next_j = 0;next_i++;}bool set0 = matrix[i][j] == 0;   // 記錄當(dāng)前狀態(tài)，是否需要清零BFS(ref matrix, next_i, next_j); // 繼續(xù)遍歷// 最后執(zhí)行清零if (set0) {for (int p = 0; p < n; p++) matrix[i][p] = 0;for (int q = 0; q < m; q++) matrix[q][j] = 0;}}
}

• 時(shí)間復(fù)雜度：$O(m\times n)$。
• 空間復(fù)雜度：由矩陣中 0 出現(xiàn)的次數(shù)決定。

??該方法依據(jù)元素記錄，因此當(dāng)矩陣中 0 出現(xiàn)次數(shù)過多時(shí)，會(huì)有重復(fù)操作，只適合處理稀疏 0 矩陣。

??矩陣中 0 過于密集時(shí)，使用記錄行列的方式會(huì)更好些，但可能需要更多的空間和遍歷次數(shù)。