一天一道LeetCode
本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github
欢迎大家关注我的新浪微博，我的新浪微博
欢迎转载，转载请注明出处
（一）题目
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
（二）解题
题目大意：给定一个M*N的数组，如果（i，j）为0，则将第i行第j列全部元素置为0。
这道题目意思很简单，如果考虑到用辅助空间来计算就超级简单了，本题不允许用辅助空间！
那么，我们换个思路，利用矩阵自身来存储需要修改的信息。
这里我们考虑将需要修改的行列信息存储在第0行和第0列。具体见代码：
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int row = matrix.size();
if(row==0) return;
int col = matrix[0].size();
int R0flag = false;//记录第0行是否存在0
int C0flag = false;//记录第0列是否存在0
for(int i = 0 ; i< row ; i++)
{
if(matrix[i][0]==0) {C0flag=true;break;}//扫描第0列
}
for(int i = 0 ; i< col ; i++)
{
if(matrix[0][i]==0) {R0flag=true;break;}//扫描第0行
}
//扫描整个数组，用matrix[i][0]保存需要修改的列， matrix[0][j]保存需要修改的行
for(int i = 0 ; i < row ;i++)
{
for(int j = 0 ; j < col ; j++)
{
if(matrix[i][j] == 0)
{
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
//修改1~col-1列
for(int i = 1 ; i< row ; i++)
{
if(matrix[i][0]==0){
for(int j = 0 ; j< col ; j++)
{
matrix[i][j]=0;
}
}
}
//修改1~row-1行
for(int i = 1 ; i< col ; i++)
{
if(matrix[0][i]==0){
for(int j = 0 ; j< row ; j++)
{
matrix[j][i]=0;
}
}
}
//修改第0行和第0列
if(R0flag){
for(int i = 0 ; i < col ; i++) matrix[0][i] =0;
}
if(C0flag){
for(int i = 0 ; i < row ; i++) matrix[i][0] =0;
}
}
};