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.
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