logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
leetcode中那道Set Matrix Zeroes怎么做
avatar
leetcode中那道Set Matrix Zeroes怎么做# JobHunting - 待字闺中
k*r
1 楼
是leetcode online judgement中的题目
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.
怎么弄出时间为O(mn),空间为O(1)的解法呢？
avatar
g*e
2 楼
不难吧，仔细想想
avatar
O*i
3 楼
复用第一行第一列作为判断是否要置0的内存空间就可以了
因为第一行和第一列相交于(0, 0)，
如果(0, 0)算第一行但不算第一列，你另外加用一个变量来辅助第一列

entire

【在 k*******r 的大作中提到】
: 是leetcode online judgement中的题目
: 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.
: 怎么弄出时间为O(mn),空间为O(1)的解法呢？
avatar
k*r
4 楼
很巧妙阿，多谢
avatar
p*2
5 楼
只用第一行就可以了。
avatar
f*d
6 楼
那第一行和第一列原来的值放哪里？是不是需要先搜索出某一行和某一列原本就需要置
零才可以用它？

【在 O******i 的大作中提到】
: 复用第一行第一列作为判断是否要置0的内存空间就可以了
: 因为第一行和第一列相交于(0, 0)，
: 如果(0, 0)算第一行但不算第一列，你另外加用一个变量来辅助第一列
:
: entire
avatar
g*u
7 楼
The same question: how about the original values of the first row and first
column if none of their numbers are zeros.
avatar
r*e
8 楼
应该用你扫到的第一个0所在的行和列来存。

first

【在 g*******u 的大作中提到】
: The same question: how about the original values of the first row and first
: column if none of their numbers are zeros.
avatar
z*3
9 楼
正解
那个常量空间复杂度就用来存这个第一个0的位置

【在 r*****e 的大作中提到】
: 应该用你扫到的第一个0所在的行和列来存。
:
: first
avatar
r*e
10 楼
如果对应的行/列有零，那么原来的值本来也要被零覆盖
如果行列都没有零，那原值也不受影响

first

【在 g*******u 的大作中提到】
: The same question: how about the original values of the first row and first
: column if none of their numbers are zeros.
avatar
r*e
11 楼
不必须吧，任意一行加一列都行，事先扫一下这行/列有没有零就行了

【在 r*****e 的大作中提到】
: 应该用你扫到的第一个0所在的行和列来存。
:
: first
avatar
r*e
12 楼
扫一遍下来不更好吗？反正要整个matrix过一遍的。

【在 r*******e 的大作中提到】
: 不必须吧，任意一行加一列都行，事先扫一下这行/列有没有零就行了
avatar
s*r
13 楼
这个貌似一定要再搞个矩阵来纪录吧？或者再搞个vector什么的纪录位置。
avatar
c*w
14 楼
用第0行第0列不就OK

【在 s**********r 的大作中提到】
: 这个貌似一定要再搞个矩阵来纪录吧？或者再搞个vector什么的纪录位置。
avatar
s*r
15 楼
哦哦，我2了。
顺便搭车问一下，8皇后的循环解法怎么做？

【在 c********w 的大作中提到】
: 用第0行第0列不就OK
avatar
c*w
16 楼
哥只会递归
哥看来得去学习下循环的解法了……

【在 s**********r 的大作中提到】
: 哦哦，我2了。
: 顺便搭车问一下，8皇后的循环解法怎么做？
avatar
z*3
17 楼
扫一遍和扫十遍都是一样的复杂度
只要不是扫n遍就行
而且分开的话，代码好写很多，条理也清晰

【在 r*****e 的大作中提到】
: 扫一遍下来不更好吗？反正要整个matrix过一遍的。
avatar
b*g
18 楼
最naive的方法就是先用两个变量记录第一行和第一列是不是有0，
然后用第一行存哪一列有0，用第一列存哪一行有0
这题算是leetcode最简单的题了吧？

entire

【在 k*******r 的大作中提到】
: 是leetcode online judgement中的题目
: 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.
: 怎么弄出时间为O(mn),空间为O(1)的解法呢？
avatar
b*g
19 楼
没关系的

first

【在 g*******u 的大作中提到】
: The same question: how about the original values of the first row and first
: column if none of their numbers are zeros.
avatar
s*r
20 楼
呜呜，我也是，只会递归。。。
递归那几道题目，我只会递归，等你会循环得时候，能不能告诉我一下怎么做得？

【在 c********w 的大作中提到】
: 哥只会递归
: 哥看来得去学习下循环的解法了……
相关阅读
查工资水平的网站求推荐公司挂opt被举报该怎么办G家面经（已被HC挂，求分析）为什么面试要问那些工作中从来不会遇到的算法？又开始炒作 刘强东， 程序员 = 垃圾职业？关于Google导师的推荐信毕业之后短暂工作一小段时间不写background check会有事吗关于毁约，已经negotiate两次offer然后邮件回复答应了求问各位大牛，fresh graduate投facebook google和apple是找人refer好还是在学校的careerlink上投比较好请问这个3sumClosest找工作来吐个槽linkedin 上的recruiter上班第一天请教offer选择Re: 实在不知道我的老板是不是傻逼 还是我傻逼 (转载)DC在招IT工 ActioNet Positions。。。 (转载)急！在线等，我同学叫游诗婷，要来美国了。要改名字吗？今天 Google超越苹果成为世界最有价值品牌nootcoder剑走偏锋：地铁十八摸吸引北美高端人才回流
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。