矩阵置零这个题目,如何做到空间复杂度为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
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
leetcode 73
点赞 回复 分享
发布于 2017-08-31 15:57
遍历矩阵,用每一行或者每一列的第一个来记录这一行或者这一列是否需要置0,第二次遍历的时候,根据第一个数,来处理其他的元素。
点赞 回复 分享
发布于 2017-08-31 16:00

相关推荐

无敌虾孝子:喜欢爸爸还是喜欢妈妈
点赞 评论 收藏
分享
11-03 14:38
重庆大学 Java
AAA求offer教程:我手都抬起来了又揣裤兜了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务