题目描述
给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
样例
输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]
输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
算法1
暴力解决:
1、申请一个新矩阵,将原矩阵复制过去。
2、判断原矩阵中某一个位置是否为0,如果为0,则将其所在行列在新矩阵中赋值。
3、将新矩阵赋值回原矩阵
时间复杂度:O(n^3) 空间复杂度:O(mn)
C++ 代码
class Solution {
public:
/*
暴力解决:
1、申请一个新矩阵,将原矩阵复制过去。
2、判断原矩阵中某一个位置是否为0,如果为0,则将其所在行列在新矩阵中赋值。
*/
void setZeroes(vector<vector<int>>& matrix) {
int nLen=matrix[0].size(),nWidth=matrix.size();
vector<vector<int>> newMatrix(matrix);
for(int i=0;i<nWidth;i++)
{
for(int j=0;j<nLen;j++)
{
if(matrix[i][j]==0)
{
for(int k=0;k<nLen;k++) newMatrix[i][k]=0;
for(int k=0;k<nWidth;k++) newMatrix[k][j]=0;
}
}
}
matrix.swap(newMatrix);
}
};
算法2
两个一维数组分别记录行、列是否需要被赋零:
1、创建两个一维数组,一个用来记录需要被赋零的行,一个用来记录需要被赋零的列。
如果当前行(列)需要被赋零,则将其标记,等之后遍历时再赋零。
2、遍历矩阵,如果当前位置是0,则将其行列在一维数组中进行标记
3、遍历矩阵,同时判断该行列是否被标记,标记则赋零
时间复杂度:O(nm) 空间复杂度:O(n+m)
C++ 代码
class Solution {
public:
/*
暴力解决:
1、申请一个新矩阵,将原矩阵复制过去。
2、判断原矩阵中某一个位置是否为0,如果为0,则将其所在行列在新矩阵中赋值。
3、将新矩阵赋值回原矩阵
时间复杂度:O(n^3) 空间复杂度:O(mn)
两个一维数组分别记录行、列是否需要被赋零:
1、创建两个一维数组,一个用来记录需要被赋零的行,一个用来记录需要被赋零的列。
如果当前行(列)需要被赋零,则将其标记,等之后遍历时再赋零。
2、遍历矩阵,如果当前位置是0,则将其行列在一维数组中进行标记
3、遍历矩阵,同时判断该行列是否被标记,标记则赋零
时间复杂度:O(nm) 空间复杂度:O(n+m)
*/
void setZeroes(vector<vector<int>>& matrix) {
int nLen=matrix[0].size(),nWidth=matrix.size();
vector<bool>flagCol(nLen,false);
vector<bool>flagRow(nWidth,false);
for(int i=0;i<nWidth;i++)
{
for(int j=0;j<nLen;j++)
{
if(matrix[i][j]==0)
{
flagCol[j]=true;
flagRow[i]=true;
}
}
}
for(int i=0;i<nWidth;i++)
{
for(int j=0;j<nLen;j++)
{
if(flagCol[j]||flagRow[i])
{
matrix[i][j]=0;
}
}
}
}
};
算法3
偷鸡技巧:
1、偷矩阵的第一行第一列的空间用来记录两个标记数组
2、此时第一行第一列是否需要赋零需要进行单独处理,因此设置两个变量来标记
3、两次遍历确定行、列两个标记数组
4、根据标记数组先处理[1-m][1-n],即除掉第一行第一列的其他位置
5、处理第一行第一列
时间复杂度:O(nm)
空间复杂度:O(1),"偷鸡":偷原矩阵的空间
C++ 代码
class Solution {
public:
/*
Ⅰ 暴力解决:
1、申请一个新矩阵,将原矩阵复制过去。
2、判断原矩阵中某一个位置是否为0,如果为0,则将其所在行列在新矩阵中赋值。
3、将新矩阵赋值回原矩阵
时间复杂度:O(n^3) 空间复杂度:O(mn)
Ⅱ 两个一维数组分别记录行、列是否需要被赋零:
1、创建两个一维数组,一个用来记录需要被赋零的行,一个用来记录需要被赋零的列。
如果当前行(列)需要被赋零,则将其标记,等之后遍历时再赋零。
2、遍历矩阵,如果当前位置是0,则将其行列在一维数组中进行标记
3、遍历矩阵,同时判断该行列是否被标记,标记则赋零
时间复杂度:O(nm) 空间复杂度:O(n+m)
Ⅲ 偷鸡技巧:
1、偷矩阵的第一行第一列的空间用来记录两个标记数组
2、此时第一行第一列是否需要赋零需要进行单独处理,因此设置两个变量来标记
3、两次遍历确定行、列两个标记数组
4、根据标记数组先处理[1,m][1,n],即除掉第一行第一列的其他位置
5、处理第一行第一列
时间复杂度:O(nm)
空间复杂度:O(1),"偷鸡":偷原矩阵的空间
*/
void setZeroes(vector<vector<int>>& matrix) {
int nLen=matrix[0].size(),nWidth=matrix.size();
// 单独处理第一行、第一列
int nRow=1,nCol=1;
for(int i=0;i<nLen;i++) if(!matrix[0][i]) nRow=0; // 如果该行有一列为0,则表示该行全部需要赋值为0
for(int i=0;i<nWidth;i++) if(!matrix[i][0]) nCol=0; // 如果该列有一行为0,则表示该列全部需要赋值为0
// 确定标记数组
for(int i=1;i<nWidth;i++) // 从[1,0]开始向右看([1,0] [1,1] [1,2]),如果该行有0,则表示该行需要全部赋值为0
{
for(int j=0;j<nLen;j++)
{
if(matrix[i][j]==0)
{
matrix[i][0]=0; // 用第一列来记录该行是否需要赋值为0
}
}
}
for(int j=1;j<nLen;j++) // 从[0,1]开始向下看([0,1] [1,1] [2,1]),如果该列有0,则表示该列需要全部赋值为0
{
for(int i=0;i<nWidth;i++)
{
if(matrix[i][j]==0)
{
matrix[0][j]=0; // 用第一行来记录该列是否需要赋值为0
}
}
}
// 不能先处理第一行第一列:先处理第一行第一列的话,则会导致第一行第一列存储的标记数组被污染,则无法进行[1-m][1-n]的处理
for(int i=1;i<nWidth;i++)
{
for(int j=1;j<nLen;j++)
{
if(matrix[i][0]==0||matrix[0][j]==0) matrix[i][j]=0;
}
}
// 处理第一行
if(!nRow)
{
for(int i=0;i<nLen;i++)
{
matrix[0][i]=0;
}
}
// 处理第一列
if(!nCol)
{
for(int i=0;i<nWidth;i++)
{
matrix[i][0]=0;
}
}
}
};