LeetCode 73. Set Matrix Zeroes

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

Example 1:

Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:

Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Follow up:

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?
解析：
给定一个m*n的矩阵，如果某一个元素为0，则元素所在的行和列的所有元素都置为0.
解法1:
遍历每个元素，分别采用两个set记录需要置0的行序号和列序号。
具体代码如下：
[cc lang=”C++”]
class Solution {
public:
void setZeroes(vector>& matrix) {
int row_len = matrix.size();
int col_len = matrix[0].size();
set row_flag;
set col_flag;
for(int i=0; i < row_len; i++) { for(int j=0; j
解法2:
继续优化代码，空间复杂度为常数级别。
考虑使用matrix数组存放标记信息，如果某一行包含0，则在当前行的第一个元素设置为0作为标记位；如果某一列包含0，则在当前列的第一个元素设置为0作为标记位。但是第0行和第0列公用同一个单元，这样会有冲突，所以单独设置一个变量来存放第0列。
具体代码如下：
[cc lang=”C++”]
class Solution {
public:
void setZeroes(vector>& matrix) {
int row_len = matrix.size();
int col_len = matrix[0].size();
int col0 = 1;//设置第0列的标记位
for(int i=0; i < row_len; i++) { if(matrix[i][0] == 0) col0 = 0; for(int j=1; j < col_len; j++) { if(matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for(int i =row_len-1; i >= 0; i–)
{
for(int j = col_len-1; j>=1; j–)
if(matrix[i][0] == 0 || matrix[0][j] == 0)
{
matrix[i][j] = 0;
}
if(col0 == 0)
matrix[i][0] = 0;
}
}
};
[/cc]
运行结果：