【算法】矩阵置零

针对这道力扣 写一点笔记。

题目分析

首先这类矩阵题目，在初次接触力扣时感觉很难，目前看来主要框架就是双循环，注意分析行和列即可。

这道题最难的地方是他限制了对存储空间的使用，因此需要实现原地计算就要合理设计算法。

如果使用O(1)的存储空间，就需要利用原矩阵的行和列去存储信息，方法二中给出的算法用到的是第一行和第一列分别存储对应列和对应行是否为0，这就造成了对第一行和第二行的改动，这种改动首先是不可逆的，其次是递增的。

如何理解不可逆？

如果第1行没有0，且最终分析的结果只有第5列有0，那么得到的结果矩阵中第5列应该是全0的，包括第一行的。此时会发现无法判定第一行原来是否有0，因为已经发生了更改。

因此需要常数的空间去记录第一行和第一列原来是否有0（方法三将两个常数变成了一个常数）

如何理解递增？

初次看到这个算法会有一个疑问，这样贸然改变第一行和第一列的数据，会对原来的数据造成影响吗？

仔细分析之后发现，如果除了第一行和第一列之外的数据有0，那么对应行和对应列本身就会被变成0，因此是无影响的，这样做只是使得原矩阵向目标矩阵更加接近。

方法三

方法三相对于方法二而言的改动就是用第一行第一列来存储第一行的信息，然后利用倒序遍历的方式使得该信息可以保留到完成上图中第二个流程。