矩阵置零这个题目,如何做到空间复杂度为O(1)

给定一个M*N的矩阵, 如果一个元素为0,则把其所在的行列的所有元素全部置为 0(无需处理输入输出)。
请原地(in-place)完成。
*原地完成: 除给定数据外,申请额外空间的复杂度为O(1)。
例:
Input:
1 1 1 0
1 1 0 1
1 1 1 1
Output:
0 0 0 0
0 0 0 0
1 1 0 0
我记得牛客有这个题目,但是找不到了,也想不到空间复杂度这么低的解法
全部评论
扫描第0行  只要有0  flag_row=true 扫描第0列 只要有0 flag_col=true 遍历所有元素  如果mat(i,j)=0,则令mat(i,0)=0 且mat(0,j)=0 遍历1~N行,如果mat(i,0)=0  该行全部元素置0 遍历1~M列,如果mat(0,j)=0 该列全部元素置0 如果falg_col=true  第0列全部置0  否则全部置1 如果flag_row=true 第0列全部置0 否则全部置1
5 回复 分享
发布于 2017-08-31 16:00
遍历矩阵,用每一行或者每一列的第一个来记录这一行或者这一列是否需要置0,第二次遍历的时候,根据第一个数,来处理其他的元素。
点赞 回复 分享
发布于 2017-08-31 16:00
leetcode 73
点赞 回复 分享
发布于 2017-08-31 15:57
https://www.nowcoder.com/practice/9ff9256075a1498fb165b583d951ebd4?tpId=46&tqId=29105&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
点赞 回复 分享
发布于 2017-08-31 15:56

相关推荐

看牛客上感觉牛油都是985/211硕,本科生都很少见呀。现在秋招有佬拿到offer了嘛
职场水母:大多数本科生都在急着谈恋爱吧,能上牛客的少之又少,倒是硕士在这里有很多,这部分人群走的路及其相似,当年都选择了考研,到现在找工作都喜欢上牛客,不得不说还是挺有远见的大家。大家都是有远见的牛马
点赞 评论 收藏
分享
芜湖e:我在这家待过,老板就一rz,能别去就别去,还在用jsp,合同也不主动给你签,上班看一下手机他就要把你叫到办公室说你,公司项目也老,还在用jsp,纯屎山代码,我干了三天就跑路了,工资也没给😅
点赞 评论 收藏
分享
08-08 14:46
郑州大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务