建站报价,外贸公司推广平台,网上查公司怎么查,常德公司做网站题目描述#xff1a;
给定一个 m x n 的矩阵#xff0c;如果一个元素为 0 #xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 示例 1#xff1a; 输入#xff1a;matrix [[1,1,1],[1,0,1],[1,1,1]]
输出#xff1a;[[1,0,1],[0,0,0],[1,0,1]]示例 2…题目描述
给定一个 m x n 的矩阵如果一个元素为 0 则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 示例 1 输入matrix [[1,1,1],[1,0,1],[1,1,1]]
输出[[1,0,1],[0,0,0],[1,0,1]]示例 2 输入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]]提示
m matrix.lengthn matrix[0].length1 m, n 200-231 matrix[i][j] 231 - 1 进阶
一个直观的解决方案是使用 O(mn) 的额外空间但这并不是一个好的解决方案。一个简单的改进方案是使用 O(m n) 的额外空间但这仍然不是最好的解决方案。你能想出一个仅使用常量空间的解决方案吗
通过次数
286.9K
提交次数
446.4K
通过率
64.3%
思路和题解
一、先遍历一次矩阵用一个数组row和一个数组col标记要置零的行和列随后再遍历一次矩阵如果矩阵所在行或列要置0那就变零。时间复杂度O(m*n)空间复杂度O(mn)
代码
class Solution {
public:void setZeroes(vectorvectorint matrix) {int mmatrix.size();int nmatrix[0].size();//记录要置零的行和列vectorint row(m,0);vectorint col(n,0);for(int i0;im;i)for(int j0;jn;j)if(matrix[i][j]0)row[i]col[j]1;for(int i0;im;i)for(int j0;jn;j)if(row[i]1||col[j]1)matrix[i][j]0;}
};
二、方法一的改进矩阵的第一行和第一列代替col和row实现O(1)空间复杂度但矩阵的第一行和第一列有交叉交叉的位置既要标记第一行是否出现零又要标记第一列是否出现零所以我们应该额外设置一个变量flagflag与matrix[0][0]一个标记第一行是否出现零一个标记第一列是否出现零。
代码
lass Solution {
public:void setZeroes(vectorvectorint matrix) {int mmatrix.size();int nmatrix[0].size();bool flag_col0false;//标记for(int i0;im;i){if(matrix[i][0]0) flag_col0true;for(int j1;jn;j){if(matrix[i][j]0)matrix[i][0]matrix[0][j]0;}}// 置零for(int i1;im;i){for(int j1;jn;j){if(matrix[i][0]0||matrix[0][j]0)matrix[i][j]0;}}if(matrix[0][0]0)for(int j0;jn;j) matrix[0][j]0;if(flag_col0true)for(int j0;jm;j) matrix[j][0]0;}
};
