网站管理助手 1004,巩义网站公司,企业1级域名网站怎么做,北京seo网站优化培训题目链接#xff1a;leetcode 73
1.题目
给定一个 m x n 的矩阵#xff0c;如果一个元素为 0 #xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
2.示例
1#xff09;示例 1#xff1a; 输入#xff1a;matrix [[1,1,1],[1,0,1],[1,1,1]] 输出leetcode 73
1.题目
给定一个 m x n 的矩阵如果一个元素为 0 则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
2.示例
1示例 1 输入matrix [[1,1,1],[1,0,1],[1,1,1]] 输出[[1,0,1],[0,0,0],[1,0,1]]
2示例 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]]
3提示 m matrix.length n matrix[0].length 1 m, n 200 -231 matrix[i][j] 231 - 1
3.分析
首先有一个最直观的方法就是使用O(m*n)的额外空间在另外一个数组上进行修改。在此基础上我们可以分别存储某一行某一列是否包含零这样就使用了O(mn)的额外空间。那么我们在上述方法的基础上使用matrix的第一排和第一列分别表示该格子所在的行或列是否包含零因为当该行或列也存在0时候这个格子也会变成0。同时在最开始记录第一行和第一列是否原本就包含0即可。
4.代码
class Solution {
public:mapint,int map1,map2;void setZeroes(vectorvectorint matrix) {//1.O(nm)// for(int i0;imatrix.size();i)// for(int j0;jmatrix[0].size();j)// if(matrix[i][j]0){// map1[i]1;// map2[j]1;// }// for(int i0;imatrix.size();i)// for(int j0;jmatrix[0].size();j)// if(map1.count(i)!0||map2.count(j)!0)// matrix[i][j]0;//2.常量级bool row1false,col1false;int mmatrix.size(),nmatrix[0].size();for(int i0;im;i)if(matrix[i][0]0) col1true;for(int i0;in;i)if(matrix[0][i]0) row1true;for(int i1;im;i)for(int j1;jn;j)if(matrix[i][j]0){matrix[0][j]0;matrix[i][0]0;} for(int i1;im;i)for(int j1;jn;j)if(matrix[0][j]0||matrix[i][0]0) matrix[i][j]0;if(row1)for(int i0;in;i) matrix[0][i]0;if(col1)for(int i0;im;i) matrix[i][0]0;}
};
