Skip to content

Latest commit

 

History

History

072. Set Matrix Zeroes

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

矩阵题,问题可概括为:只要有一个元素等于0, 其所在行与所在列皆为0.

看上去挺容易嘛,没说有序的事,那就从头遍历呗,遇到等于0的,就将其行列全弄成0即可。

等等,如果遇到第一个0,就这么干的话,后面有没有0,我还能知道吗?

原来,这道题的难度在于: 第一次遍历不能破坏矩阵原数据

那我们只能做标记了,遇到0,就记录其行列?那所耗空间就不是恒定的了。要想恒定,就得利用已有空间

再看看参数,一个嵌套vector的引用,得了,题目的意思很明显,就是让你利用矩阵本身的空间。

可是咱们不是不能破坏矩阵吗,这不矛盾吗。回想之前做的题,可以知道一个基本的规律:

虽然不能破坏还未迭代的空间,但是已经迭代过的空间,完全可以利用。

如果我们一行一行的遍历,那么第一行是一定不会回头看的。

好了,我们将第一行作为标记位,扫描到0,则记录matrix[0][j] = 0;。但除了记录列数,还需要记录行数。

这时,我们就需要第一列也作为标记位,可第一列的问题在于,每一次按行迭代,都会访问第一列,如何不被标记值所干扰呢?

若第一列本身有0,那么这一列全部都该是0;若第一列本身没0,出现0全是因为标记位,才会出现干扰。

针对上述这种情况,我们不得已,只好在第一列这个标记之上,再弄一个标记。一个bool值,记录第一列本身到底有无0.

恰好,按行遍历时,第一列每次都是扫描一行时的第一个元素,此刻没有干扰,可以记录 true or false (本身有无0).


总结一下,总共两个层次的标记,

  • 第一行第一列,皆为标记其余行其余列是否应为0。
  • bool值,标记第一列是否该为0。
  • 第一行由于不曾干扰,所以不必标记。
  • 上一条,如果发生了第二次从头迭代,则会不被满足。故我们第二次迭代(按标记赋值),需要从尾部开始,逆向迭代。

以上就是该题的几个关键点。最终的代码非常简单。时刻注意第一列的特殊性即可。