题目描述
Given a m x n 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(m n) 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?
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
vector<bool> col,row;
col.resize(matrix[].size(), false);
row.resize(matrix.size(), false);
for (int i = ; i < matrix.size(); ++i)
{
for (int j = ; j < matrix[i].size();++j)
{
if(matrix[i][j]==)
{
col[j]=true;
row[i]=true;
}
}
}
for (int i = ; i < matrix.size(); ++i)
{
for (int j = ; j < matrix[i].size();++j)
{
if(col[j]||row[i])
{
matrix[i][j]=;
}
}
}
}
};
最优解法：
首先判断第一行和第一列是否有元素为0，而后利用第一行和第一列保存状态，最后根据开始的判断决定是否将第一行和第一列置0
//时间复杂度O(mn)，空间复杂度O(1)
//利用第一行和第一列的空间做记录
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
const int row = matrix.size();
const int col = matrix[].size();
bool row_flg = false, col_flg = false; //判断第一行和第一列是否有零，防止被覆盖
for (int i = ; i < row; i++)
if ( == matrix[i][]) {
col_flg = true;
break;
}
for (int i = ; i < col; i++)
if ( == matrix[][i]) {
row_flg = true;
break;
}
//遍历矩阵，用第一行和第一列记录0的位置
for (int i = ; i < row; i++)
for (int j = ; j < col; j++)
if ( == matrix[i][j]) {
matrix[i][] = ;
matrix[][j] = ;
}
//根据记录清零
for (int i = ; i < row; i++)
for (int j = ; j < col; j++)
if ( == matrix[i][] || == matrix[][j])
matrix[i][j] = ;
//最后处理第一行
if (row_flg)
for (int i = ; i < col; i++)
matrix[][i] = ;
if (col_flg)
for (int i = ; i < row; i++)
matrix[i][] = ;
}
};