leetcode-73-矩阵置零
2024-10-18 07:08:12
题目描述：
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1:
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶:
- 一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
- 你能想出一个常数空间的解决方案吗？
要完成的函数：
void setZeroes(vector<vector<int>>& matrix)
说明：
1、这道题给定一个二维vector，要求把矩阵中0元素的行和列上的所有元素都置0，要求原地修改。
2、这道题其实如果先存储0元素的位置，多费点空间，这道题是可以很迅速地解决的。
空间复杂度是O(mn)的代码如下：
void setZeroes(vector<vector<int>>& matrix)
{
int hang=matrix.size(),lie=matrix[0].size();
vector<int>record;//存储0元素的行坐标、列坐标
for(int i=0;i<hang;i++)
{
for(int j=0;j<lie;j++)
{
if(matrix[i][j]==0)
{
record.push_back(i);//行坐标在前
record.push_back(j);//列坐标在后
}
}
}
for(int i=0;i<record.size();i+=2)
{
for(int j=0;j<lie;j++)//先处理同一行的
matrix[record[i]][j]=0;
for(int j=0;j<hang;j++)//再处理同一列的
matrix[j][record[i+1]]=0;
}
}
上述代码实测44ms，beats 99.66% of cpp submissions。时间复杂度是可以满足的。
改进：
如果想改成O(m+n)的时间复杂度，那要怎么做？
也很容易，我们不要记0元素的位置了，我们记哪几行哪几列需要置0。
代码也很容易，如下：
void setZeroes(vector<vector<int>>& matrix)
{
int hang=matrix.size(),lie=matrix[0].size();
vector<int>hangrecord,lierecord;
for(int i=0;i<hang;i++)
{
for(int j=0;j<lie;j++)
{
if(matrix[i][j]==0)
{
hangrecord.push_back(i);//第i行要置为0
break;
}
}
}
for(int j=0;j<lie;j++)
{
for(int i=0;i<hang;i++)
{
if(matrix[i][j]==0)
{
lierecord.push_back(j);//第j列要置为0
break;
}
}
}
for(int i=0;i<hangrecord.size();i++)//逐个处理行
{
matrix[hangrecord[i]]=vector<int>(lie,0);//整一行置为0的vector
}
for(int i=0;i<lierecord.size();i++)//逐个处理列
{
for(int j=0;j<hang;j++)
{
matrix[j][lierecord[i]]=0;
}
}
}
上述代码实测44ms，beats 99.66% of cpp submissions。
其实笔者看到其他博客还有常数空间复杂度的做法，但这两天状态不是很好，也就没仔细钻研，等之后再来补吧。
最新文章
- hdu 1048 The Hardest Problem Ever
- LightOJ 1247 Matrix Game (尼姆博弈)
- 如何查看连接mysql的ip地址
- share干什么的
- System Operations on AWS - Lab 1W - Creating EC2 (Windows)
- BZOJ 1651: [Usaco2006 Feb]Stall Reservations 专用牛棚
- SQL2005性能分析一些细节功能你是否有用到?(三)
- POJ3468--A Simple Problem with Integers--线段树/树状数组 改段求段
- SQL复习五（索引）
- input 显示/隐藏密码
- ubuntu追加磁盘空间
- LOJ #6041. 事情的相似度
- Spring Boot中使用Swagger2构建RESTful APIs
- Shell学习之条件测试(四)
- 洛谷 P1140 相似基因(DP)
- jdk自动安装java_home 无法修改解决方法
- UVALive 6911 Double Swords 树状数组
- CSS-图像映射
- 对JAVA RMI的认识
- java模板导出PDF