73 Set Matrix Zeroes

https://leetcode.com/problems/set-matrix-zeroes/#/description

Given amxnmatrix, 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?

分析及代码

首先是自己想的方法

要constant extra space就只能想到利用板子自己来记录信息了,但是第一行和第一列自己的信息会被其他的覆盖掉,所有要单复记录他

  • 记录第一行有没有0
  • 记录第一列有没有空
  • 对于由1开始的行列,遍历整个板子,如果该位是0,把matrix[i][0]和matrix[0][j]都设置为0
  • 再次遍历由1开始的板子,如果matrix[i][0]和matrix[0][j]任一为0,就设置该位为0
  • 如果第一行有0,设置第一行为0
  • 如果第一列有0,设置第一列为0

反正也是对的,就是丑

然后看了discuss有一个简洁一点的方法: https://discuss.leetcode.com/topic/5056/any-shorter-o-1-space-solution

results matching ""

    No results matching ""