Set Matrix Zeroes const space solution - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Set Matrix Zeroes const space solution

Set Matrix Zeroes const space solution# JobHunting - 待字闺中

S*n2013-05-01 07:05

1 楼

Given a m x n matrix, if an element is 0, set its entire row and column to 0
. Do it in place.
Could you devise a constant space solution?
谁给点提示，一下想不出来

n*r2013-05-01 07:05

2 楼

用搜到的第一个为0的row和col，存后面为0的点的坐标
然后根据这个row和col里的0来set zeros

S*n2013-05-01 07:05

3 楼

不是太明白，能不能稍微说详细点？

s*s2013-05-01 07:05

4 楼

我是这样做的
第一遍：找到整个matrix的最大值，然后把所有的0编程最大值+1，
第二遍：
对所有最大值+1的元素，将行列变成0
第三编：
把所有最大值+1的元素变成0
O(n)，memory: O(1)

0

【在 S******n 的大作中提到】

: Given a m x n matrix, if an element is 0, set its entire row and column to 0
: . Do it in place.
: Could you devise a constant space solution?
: 谁给点提示，一下想不出来

r*e2013-05-01 07:05

5 楼

和下面说的思想一样，但是要注意一点，code有注释，否则所有entry都变成0了。
for (row=0; rowfor (col=0; colif (mat[row][col]==0) {
if (!foundZero) {
foundZero=true;
therow=row;
thecol=col;
} else {
mat[therow][col]=0;
mat[row][thecol]=0;
}
}
}
}
if (!foundZero) return;//do nothing
for (col=0; colif (mat[therow][col]==0 && col!=thecol) {//col!=thecol is meant to set
for thecol at last to avoid setting all elements to 0
for (row=0; rowmat[row][col]=0;
}
}
for (row=0; rowfor (col=0; colif (mat[row][thecol]==0) mat[row][col]=0;
}
}
/* do this at last, o/w all elements will be set to 0 */
for (row=0; rowmat[row][thecol]=0;

【在 n********r 的大作中提到】

: 用搜到的第一个为0的row和col，存后面为0的点的坐标
: 然后根据这个row和col里的0来set zeros