Problem: 73. 矩阵置零
题目描述
思路
思路1:利用一个等大的矩阵判定
复制一个与原始矩阵一样大的矩阵temp,遍历temp时若temp[i][j] == 0,则将martix对应的行与列均设置为0
思路2:利用两个一维矩阵判定
利用两个bool类型的一维矩阵marxRow,markCol分别表示行于列,若martix[i][j] == 0时则marxRow[i] == true;markCol[j] == true;再次遍历martix时若marxRow[i] == true;markCol[j] == true则将martix[i][j]设为0
思路3:利用原始矩阵第一行与列判定
1.利用两个bool变量用来判断martix的第一行、列是否存在0(最后利用两个变量单独处理、将martix的第一行、列设为0);
2.从martix的第一行、列开始,若martix[i][j] == 0则将martix[i][0]与martix[0][j]均设为0;再次从martix的第一行、列遍历时,若martix[i][0] == 0 || martix[0][j] == 0则将martix[i][j]设为0
3.最后利用两个变量单独处理、将martix的第一行、列设为0
复杂度
其中 m m m为martix的行数, n n n为martix的列数
思路1:
时间复杂度:
O ( m × n ) O(m \times n) O(m×n)
空间复杂度:
O ( m × n ) O(m \times n) O(m×n)
思路2:
时间复杂度:
O ( m × n ) O(m \times n) O(m×n)
空间复杂度:
O ( m + n ) O(m + n) O(m+n)
思路3:
时间复杂度:
O ( m × n ) O(m \times n) O(m×n)
空间复杂度:
O ( 1 ) O(1) O(1)
Code
思路1:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int row = matrix.size();
int col = matrix[0].size();
vector<vector<int>> temp(row, vector<int>(col));
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
temp[i][j] = matrix[i][j];
}
}
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (temp[i][j] == 0) {
//Set the current row to 0
for (int m = 0; m < col; ++m) {
matrix[i][m] = 0;
}
//Set the current colcumn to 0
for (int n = 0; n < row; ++n) {
matrix[n][j] = 0;
}
}
}
}
}
};
思路2:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int row = matrix.size();
int col = matrix[0].size();
vector<bool> markRow(row);
vector<bool> markCol(col);
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (matrix[i][j] == 0) {
markRow[i] = true;
markCol[j] = true;
}
}
}
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (markRow[i] || markCol[j]) {
matrix[i][j] = 0;
}
}
}
}
};
思路3:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int row = matrix.size();
int col = matrix[0].size();
bool markRow0 = false;
bool markCol0 = false;
//Check whether 0 exists in the first row or column
for (int i = 0; i < row; ++i) {
if (matrix[i][0] == 0) {
markCol0 = true;
}
}
for (int j = 0; j < col; ++j) {
if (matrix[0][j] == 0) {
markRow0 = true;
}
}
for (int i = 1; i < row; ++i) {
for (int j = 1; j < col; ++j) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < row; ++i) {
for (int j = 1; j < col; ++j) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
//Handle the first row and column separately
if (markRow0) {
for (int j = 0; j < col; ++j) {
matrix[0][j] = 0;
}
}
if (markCol0) {
for (int i = 0; i < row; ++i) {
matrix[i][0] = 0;
}
}
}
};