題意

一個矩陣，如果位置[i,j]$[i, j]$上有一個元素為0，那么就將第i行的所有元素置為0，將第j列的所有元素置為0。

思路

算法1

O(m+n)$O(m + n)$空間。

開一個row[]和col[]分別記錄哪些行，哪些列需要置為0即可。

算法2

O(1)$O(1)$空間。

從上一個算法我們可以知道必須要保存需要update的行和列，但是只能額外開O(1)$O(1)$的空間，那么我們只有利用現(xiàn)有的空間了。

于是，類似于十字交叉鏈表的思想，我們可以用第一行和第一列來記錄需要update的行和列。

如下圖所示：

細節(jié)

在算法2中，我們需要注意這樣一個問題，我們用第一行的某一個元素a[0,j]=0$a[0, j] = 0$來表示第j列需要全部更新為0，第一列的a[i,0]$a[i, 0]$來表示第i行需要全部更新為0。但是存在一個問題就是我們的a[0,0]$a[0, 0]$這樣的話就需要同時表示第一行和第一列的更新情況了，所以單獨開一個變量r和c來記錄第一行和第一列的更新情況。

代碼

algorithm 1

algorithm 2