Leetcode 73 - Set Matrix Zeroes（Array）

题意

一个矩阵，如果位置[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)$的空间，那么我们只有利用现有的空间了。

于是，类似于十字交叉链表的思想，我们可以用第一行和第一列来记录需要update的行和列。

如下图所示：

细节

在算法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