leetcode73矩阵置零
2024-09-05 11:00:29
https://leetcode-cn.com/problems/set-matrix-zeroes/
解答：
两种方法时间复杂度都为O(mn)
O(m+n)空间方法：
用两个容器储存为0的行和列
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
//O(m+n)额外空间，常数空间？？？
set<int> rse,cse;
int r=matrix.size();int c=matrix[].size();
for(int i=;i<r;i++){
for(int j=;j<c;j++){
if(matrix[i][j]==){
rse.insert(i);
cse.insert(j);
}
}
}
while(!rse.empty()){
int temp=*rse.begin();
for(int j=;j<c;j++){
matrix[temp][j]=;
}
rse.erase(rse.begin());
}
while(!cse.empty()){
int temp=*cse.begin();
for(int i=;i<r;i++){
matrix[i][temp]=;
}
cse.erase(cse.begin());
}
}
};
常数空间方法：
对于第0行和第0列的数据如果有0，则标记isrow=true, iscol=true来记录是否为0；
对于1~m行和1~n列的数据如果有0，则将其标注在第0行，第0列；即
i : ~m-
j: ~n-
if(matrix[i][j]==)
matrix[i][]=,matrix[][j]=;
C++ code：
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
//常数空间解决方案
//标记第0行和第0列是否为0；
bool isrow=false;
bool iscol=false;
int r=matrix.size();
int c=matrix[].size();
for(int j=;j<c;j++){
if(matrix[][j]==){
isrow=true;break;
}
}
for(int i=;i<r;i++){
if(matrix[i][]==){
iscol=true;break;
}
}
//标记1~n列是否为0，将结果放入第0行和第0列；
for(int i=;i<r;i++){
for(int j=;j<c;j++){
if(matrix[i][j]==){
matrix[i][]=;
matrix[][j]=;
}
}
}
//先将1~n行列的值替换
for(int i=;i<r;i++){
if(matrix[i][]==){
for(int j=;j<c;j++){
matrix[i][j]=;
}
}
}
for(int j=;j<c;j++){
if(matrix[][j]==){
for(int i=;i<r;i++){
matrix[i][j]=;
}
}
}
//再替换0行和0列
if(isrow){
for(int j=;j<c;j++){
matrix[][j]=;
}
}
if(iscol){
for(int i=;i<r;i++){
matrix[i][]=;
}
}
}
};
最新文章
- WPF CheckBox样式 ScrollViewer样式 WrapPanel、StackPanel、Grid布局
- HighchartsNET快速图表控件-开源
- just555 对话
- 给table行换色
- 【转】java环境配置
- 将Tab栏居中的方法
- HDU-5373 The shortest problem
- Python 的数据类型
- exp导出出现：ORA-00904: "POLTYP": invalid identifier
- 取得select框的text
- 关于t分布的证明
- 仔细讲解socket（转载https://www.zybuluo.com/phper/note/47110）
- Java 内存模型 JMM 浅析
- Python socket套接字简单例子
- mysql 开发进阶篇系列 31 工具篇(mysql连接工具与MyISAM表压缩工具)
- linux文件管理 文件权限
- HTML DOM 知识点整理（一）—— Document对象
- 非阻塞 sleep
- Image.Save()发生“GDI+ 中发生一般性错误”
- Java虚拟机学习 - 内存调优 ( 9 )