注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex73 Set Matrix Zeroes  

2015-05-16 21:45:02|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我能说开始没有看懂题目是什么意思么。。。。。

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?

这个题的思路很巧妙,不用额外的空间,直接用第一行和第一列来存储状态,我看了答案都惊呆了。
先给一个o(m+n)空间复杂度的

//正常情况下用的是o(mn)的算法,直接遍历,发现有0的话
//遍历一次矩阵,所有的元素都为0

//第一种方法是o(m+n) 开两个数组来标记该行该列是否应该置为0
void setZeroes(int** matrix, int matrixRowSize, int matrixColSize) {
if (matrix == NULL||matrix[0]==NULL)
return;
int m = matrixRowSize;
int n = matrixColSize;
int*row = (int*)malloc(m*sizeof(int));
int*col = (int*)malloc(n*sizeof(int));
int i, j;
for (i = 0; i < m; i++) //好奇葩,必须要先置为0 oj才让过
{
row[i] = 0;
}
for (j = 0; j < n; j++)
{
col[j] = 0;
}
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
if (matrix[i][j] == 0)
{
row[i] = 1;
col[j] = 1;
}
}
}
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
if (row[i] == 1 || col[j] == 1)
matrix[i][j] = 0;
}
}

}

这个在oj上很奇怪,必须新开的空间row和col必须全部初始化了才让通过。。。。。

下面是比较巧妙的常数空间完成的c代码~~~

//第二种方法是常数空间内完成
void setZeroes1(int** matrix, int matrixRowSize, int matrixColSize)
{
//用第一行和第一列来表示某一行和某一列是否应该置为0
if (matrix == NULL || matrix[0] == NULL)
return;
int m = matrixRowSize;
int n = matrixColSize;
int i, j;
bool firstRow = false; //第一行的标记
bool firstCol = false;
for (i = 0; i < m; i++)
{
if (matrix[i][0] == 0)
{
firstCol = true; //存第一列有没有0
break;
}
}
for (i = 0; i < n; i++)
{
if (matrix[0][i] == 0)
{
firstRow = true; //存第一行有没有0
break;
}
}

for (i = 1; i < m; i++)
{
for (j = 1; j < n; j++)
{
if (matrix[i][j] == 0)
{
matrix[i][0] = 0;
//从第二行 第二列开始遍历,如果遇到0,
//就将该行的第一个元素或者该列的第一个元素置为0
matrix[0][j] = 0;
}
}
}


for (i = 1; i < m; i++)
{
if (matrix[i][0] == 0)
{
for (j = 1; j < n; j++)
{
matrix[i][j] = 0;
}
}
}

for (i = 1; i < n; i++)
{
if (matrix[0][i] == 0)
{
for (j = 1; j < m; j++)
{
matrix[j][i] = 0;
}
}

}
//最后遍历第一行 和第一列
if (firstRow)
{
for (i = 0; i < n; i++)
{
matrix[0][i] = 0;
}
}
if (firstCol)
{
for (i = 0; i < m; i++)
{
matrix[i][0] = 0;
}
}

}


  评论这张
 
阅读(12)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017