k*******r
发帖数: 355 | 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)的解法呢？ |
g*********e
发帖数: 14401 | |
O******i
发帖数: 269 | 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)的解法呢？
|
k*******r
发帖数: 355 | |
p*****2
发帖数: 21240 | |
f******d
发帖数: 9 | 6 那第一行和第一列原来的值放哪里？是不是需要先搜索出某一行和某一列原本就需要置
零才可以用它？
【在 O******i 的大作中提到】
: 复用第一行第一列作为判断是否要置0的内存空间就可以了
: 因为第一行和第一列相交于(0, 0)，
: 如果(0, 0)算第一行但不算第一列，你另外加用一个变量来辅助第一列
:
: entire
|
g*******u
发帖数: 107 | 7 The same question: how about the original values of the first row and first
column if none of their numbers are zeros. |
r*****e
发帖数: 792 | 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.
|
z*******3
发帖数: 13709 | 9 正解
那个常量空间复杂度就用来存这个第一个0的位置
【在 r*****e 的大作中提到】
: 应该用你扫到的第一个0所在的行和列来存。
:
: first
|
r*******e
发帖数: 7583 | 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.
|
|
|
r*******e
发帖数: 7583 | 11 不必须吧，任意一行加一列都行，事先扫一下这行/列有没有零就行了
【在 r*****e 的大作中提到】
: 应该用你扫到的第一个0所在的行和列来存。
:
: first
|
r*****e
发帖数: 792 | 12 扫一遍下来不更好吗？反正要整个matrix过一遍的。
【在 r*******e 的大作中提到】
: 不必须吧，任意一行加一列都行，事先扫一下这行/列有没有零就行了
|
s**********r
发帖数: 8153 | 13 这个貌似一定要再搞个矩阵来纪录吧？或者再搞个vector什么的纪录位置。 |
c********w
发帖数: 2438 | 14 用第0行第0列不就OK
【在 s**********r 的大作中提到】
: 这个貌似一定要再搞个矩阵来纪录吧？或者再搞个vector什么的纪录位置。
|
s**********r
发帖数: 8153 | 15 哦哦，我2了。
顺便搭车问一下，8皇后的循环解法怎么做？
【在 c********w 的大作中提到】
: 用第0行第0列不就OK
|
c********w
发帖数: 2438 | 16 哥只会递归
哥看来得去学习下循环的解法了……
【在 s**********r 的大作中提到】
: 哦哦，我2了。
: 顺便搭车问一下，8皇后的循环解法怎么做？
|
z*******3
发帖数: 13709 | 17 扫一遍和扫十遍都是一样的复杂度
只要不是扫n遍就行
而且分开的话，代码好写很多，条理也清晰
【在 r*****e 的大作中提到】
: 扫一遍下来不更好吗？反正要整个matrix过一遍的。
|
b****g
发帖数: 192 | 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)的解法呢？
|
b****g
发帖数: 192 | 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.
|
s**********r
发帖数: 8153 | 20 呜呜，我也是，只会递归。。。
递归那几道题目，我只会递归，等你会循环得时候，能不能告诉我一下怎么做得？
【在 c********w 的大作中提到】
: 哥只会递归
: 哥看来得去学习下循环的解法了……
|
