73 矩阵置零
暴力解法
定义行数组row和列数组col表示行/列有元素0
遍历一遍矩阵,找到元素0时,更新行数组row和列数组col为true
判断row[i] || col[j]时,令矩阵为0
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector<bool> row(n, false), col(m, false);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!matrix[i][j]){
row[i] = true;
col[j] = true;
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(row[i] || col[j])
matrix[i][j] = 0;
}
}
}
};
优化1
我们可以使用矩阵的第一行和第一列代替行数组row和列数组col
但是这种代替方法会导致第一行和第一列原有的值丢失,因此我们需要保存第一行和第一列原有的值
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
// 保存第一行和第一列是否含有元素0的状态
bool firstRow = false, firstCol = false;
for(int i = 0; i < n; i++){
if(!matrix[i][0])
firstCol = true;
}
for(int j = 0; j < m; j++){
if(!matrix[0][j])
firstRow = true;
}
// 检测除了第一行和第一列外其他部分是否出现元素0
// matrix[i][0]保存第i行是否要置为0
// matrix[0][j]保存第j列是否要置为0
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
if(!matrix[i][j]){
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// 将矩阵对应行/列置为0(不包括第一行和第一列)
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
if(!matrix[i][0] || !matrix[0][j])
matrix[i][j] = 0;
}
}
// 第一行和第一列额外处理
if(firstRow){
for(int j = 0; j < m; j++)
matrix[0][j] = 0;
}
if(firstCol){
for(int i = 0; i < n; i++)
matrix[i][0] = 0;
}
}
};
优化2
优化1使用了两个标记变量firstRow和firstCol,我们还可以优化为一个标记变量
但是我觉得不是特别必要这样优化
思路见
https://leetcode.cn/problems/set-matrix-zeroes/solutions/669901/ju-zhen-zhi-ling-by-leetcode-solution-9ll7/?envType=study-plan-v2&envId=top-100-liked