LeetCode(73)Set Matrix Zeroes
题目
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
click to show follow up.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
分析
题目给定一个m∗n矩阵,要求将矩阵中值为0的元素所在的整行、整列元素均赋值为0;
重点是要求算法是本地,也就是说空间复杂度为O(1)
具体思路如下:
利用矩阵的第一行和第一列来作为辅助空间使用,不用开辟新的存储空间。
方法就是:
1.先确定第一行和第一列是否需要清零
即,看看第一行中是否有0,记下来;也同时记下来第一列中有没有0。
2.扫描剩下的矩阵元素,如果遇到了0,就将对应的第一行和第一列上的元素赋值为0
这里不用担心会将本来第一行或第一列的1改成了0,因为这些值最后注定要成为0的,比如matrix[i][j]==0,那么matrix[i][0]处在第i行,matrix[0][j]处于第j列,最后都要设置为0的。
3.根据第一行和第一列的信息,已经可以将剩下的矩阵元素赋值为结果所需的值了即,拿第一行为例,如果扫描到一个0,就将这一列都清0.
4.根据1中确定的状态,处理第一行和第一列。
如果最开始得到的第一行中有0的话,就整行清零。同理对列进行处理。
AC代码
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.empty())
return;
//求得所给矩阵的行数、列数
int m = matrix.size();
int n = matrix.front().size();
//初始化首行,首列标志位false,代表元素不为0
bool f_row = false, f_col = false;
for (int j = 0; j < n; j++)
{
if (matrix[0][j] == 0)
{
f_row = true;
break;
}//if
}//for
//记录首行、首列的状态
for (int i = 0; i < m; i++)
{
if (matrix[i][0] == 0)
{
f_col = true;
break;
}//if
}//for
//下面用原矩阵的首行和首列作为本地存储空间,因为首行首列单独处理,所以下标均从1开始
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
//如果元素(i,j)为0,则将该元素对应的首行位置(0,j)以及首列位置(i,0)值赋为0
if (matrix[i][j] == 0)
{
matrix[0][j] = 0;
matrix[i][0] = 0;
}//if
}//for
}//for
//下面根据首行,首列元素值,更新矩阵中的0
for (int j = 1; j < n; j++)
{
//找到元素为0的坐标,将矩阵中该列元素全部更改为0
if (matrix[0][j] == 0)
{
for (int i = 0; i < m; i++)
matrix[i][j] = 0;
}//if
}
for (int i = 1; i < m; i++)
{
if (matrix[i][0] == 0)
{
for (int j = 0; j < n; j++)
matrix[i][j] = 0;
}//if
}//for
//最后处理首行和首列
if (f_row)
{
for (int j = 0; j < n; j++)
matrix[0][j] = 0;
}
if (f_col)
{
for (int i = 0; i < m; i++)
matrix[i][0] = 0;
}
}
};
最新文章
- html学习第三天—— 第12章——css布局模型
- SQL Server:APPLY表运算符
- R语言基础
- oracle安装操作及遇到的错误
- c++ 二维数组传递
- POJ 2121
- 比较各大挪动门户网站淘宝、京东、网易、新浪、腾讯meta标签的异同
- linux命令(6)crontab的用法和解析
- 浏览器信息(Navigator)
- web安全:click jacking
- C#程序调用cmd执行命令(转)
- HDOJ 2102 A计划(bfs)
- 【C语言探索之旅】 第二部分第三课:数组
- Anaconda安装sasl,thrift,thrift-sasl,PyHive连接Hive
- Python类中的__init__() 和 self 的解析
- 微信小程序,天气预报(百度地图开放平台API)
- windows 如何不显示带点的文件名、文件夹?
- DQN(Deep Reiforcement Learning) 发展历程(二)
- MySQL按中文拼音排序
- win, cmd下安装mysql(win真tm难用)