leetcode 73. Set Matrix Zeroes (矩阵置0,乱搞)

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

直接放常数空间的做法。

这道题面hypereal的时候遇到过,基本思路就是用已经确定是0的位置来存储其他行和列的信息。

三点注意:

  •   (x,y)不要放任何信息,不然行和列的信息,后面处理的那个可能被覆盖掉。
  •   (x,y)位置要进行标记,否则默认的0值可能会造成歧义
  • 赋值成0的时候要分成两部分,处理的时候避免因为处理前面赋值成了0,把后面标记的行和列的标号覆盖掉。

 

 

下面有一个更精简的思路:

直接用每一行和每一列的第一个位置记录相应行和相应列的状态((0,0)点会有重合,再加一个变量记录就好)

得到信息后记得从右下角往左上更新,避免信息覆盖。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz