題目描述（中等難度）
給定一個(gè) m x n 的矩陣铛楣，如果一個(gè)元素為 0 铝宵，則將其所在行和列的所有元素都設(shè)為 0 首懈。請(qǐng)使用 原地 算法翎冲。
進(jìn)階：
- 一個(gè)直觀的解決方案是使用 O(mn) 的額外空間垂睬，但這并不是一個(gè)好的解決方案。
- 一個(gè)簡(jiǎn)單的改進(jìn)方案是使用 O(m + n) 的額外空間抗悍，但這仍然不是最好的解決方案驹饺。
- 你能想出一個(gè)僅使用常量空間的解決方案嗎？
示例 1：
示例 1
輸入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
輸出：[[1,0,1],[0,0,0],[1,0,1]]
示例2：
示例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]]
解題思路
重置零表示矩陣中如果有一個(gè)零檐春，那么將其同行同列都設(shè)為0逻淌，下圖第二行，第二列為零疟暖，使用紅色框標(biāo)識(shí)元素都需要設(shè)置成零卡儒。
解題思路
解法一 (空間復(fù)雜度 O(mn))
- 使用暴力破解，復(fù)制一個(gè)矩陣備份俐巴，遍歷復(fù)制矩陣骨望，遇到零就把當(dāng)前行和列重置零。
為何要使用復(fù)制矩陣呢欣舵？如果直接遍歷矩陣擎鸠，如果第一行第一列為零，做了重置零以后缘圈，行全部都重置為零劣光，遍歷后面的列全部都會(huì)設(shè)置成零袜蚕。
解法一
解法二 (空間復(fù)雜度O(m+n))
- 優(yōu)化一下解法一的算法，如果一個(gè)行或者列是零绢涡，我們只需要標(biāo)記一下該行或者該列為零即可牲剃。
- 使用兩個(gè)數(shù)組記錄對(duì)應(yīng)的行和列是否有零出現(xiàn)。
-
記錄結(jié)束之后雄可，遍歷矩陣凿傅，如果記錄的行或者列有零，元素重置零数苫。
解法二
解法三 (空間復(fù)雜度O(1))
- 在解法二的基礎(chǔ)上聪舒，把標(biāo)記行或者列換成標(biāo)記在矩陣上第一列和第一行。
- 遍歷第一行虐急，如果為零箱残，則同列全部置為零。
- 遍歷第一列戏仓，如果為零疚宇，則同行全部置為零亡鼠。
-
因?yàn)楸闅v列是在遍歷行之后赏殃，所以遍歷行的時(shí)候是不能遍歷第一列的。只能開始記錄一個(gè)標(biāo)記位间涵，標(biāo)記第一行仁热、第一列是否存在零。
解法三
總結(jié)
- 重置零分別使用了空間復(fù)雜度O(mn)勾哩、O(m+n)抗蠢、O(1)。
- 矩陣存在零就把行和列都設(shè)置成零思劳，就需要利用好第一行和第一列這屬性迅矛，存在零就在第一行和第一列設(shè)置零，對(duì)于特殊的首位置潜叛，需要添加標(biāo)識(shí)秽褒。
