S******n
发帖数: 132 | 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********r
发帖数: 102 | 2 用搜到的第一个为0的row和col，存后面为0的点的坐标
然后根据这个row和col里的0来set zeros |
S******n
发帖数: 132 | |
s*******s
发帖数: 1031 | 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*****e
发帖数: 792 | 5 和下面说的思想一样，但是要注意一点，code有注释，否则所有entry都变成0了。
for (row=0; row
for (col=0; col
if (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; col
if (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; row
mat[row][col]=0;
}
}
for (row=0; row
for (col=0; col
if (mat[row][thecol]==0) mat[row][col]=0;
}
}
/* do this at last, o/w all elements will be set to 0 */
for (row=0; row
mat[row][thecol]=0;
【在 n********r 的大作中提到】
: 用搜到的第一个为0的row和col，存后面为0的点的坐标
: 然后根据这个row和col里的0来set zeros
|
