题目
Given a mxn matrix, 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?
分析
空间复杂度为O(m*n)的方法很简单，直接复制矩阵，然后在新的矩阵空间中进行操作即可。
空间复杂度为O(m+n)的方法，则通过两个一维数组来分别记录每一行是否需要变为0。
空间复杂度为O(1)的方法则使用矩阵的第一行和第一列来记录，并使用两个单独的变量来记录第一行和第一列是否需要归零。在进行完矩阵其余部分的归零操作后，再据此对第一行和第一列进行归零操作。
实现
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m=matrix.size(), n=matrix[0].size();
bool row0=false, col0=false;
for(int i=0; i<m; i++)
if(matrix[i][0]==0) col0=true;
for(int j=0; j<n; j++)
if(matrix[0][j]==0) row0=true;
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
if(matrix[i][j]==0){
matrix[i][0]=0;
matrix[0][j]=0;
}
}
}
for(int i=1; i<m; i++)
if(matrix[i][0]==0)
for(int j=1; j<n; j++)
matrix[i][j]=0;
for(int j=1; j<n; j++)
if(matrix[0][j]==0)
for(int i=1; i<m; i++)
matrix[i][j]=0;
if(col0)
for(int i=0; i<m; i++)
matrix[i][0]=0;
if(row0)
for(int j=0; j<n; j++)
matrix[0][j]=0;
}
};
思考
无=_=
