p****3 发帖数: 448 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: pv3633 (pv3633), 信区: Programming
标 题: 求教矩阵改零的问题
发信站: BBS 未名空间站 (Sat May 25 12:04:34 2013, 美东)
就是遇到零就要行列都改成零的那题
只遍历一次,不用额外空间
我的想法是
遍历一次但是不包括最后一行最后一列
遇到[ij]为零时在最后一行最后一列做记号
最后遍历最后行和列把整行和列改成零
但最后一步是否使时间上大于O(n^2) |
b*****g 发帖数: 145 | 2 我也只想到了你这个做法,同问不用辅助空间的做法。
另外你这个做法还是o(n~2)的,这个不怕 |
c**********e 发帖数: 58 | 3 这样的话,如何判断最后一行和最后一列的每个元素是否为零呢?如果先遍历最后一行
和最后一列,只要行和列中各有一个元素为零,最后一行和列就全为零了。如果先遍历
其他的行和列,假设本来最后一行和最后一列全是1,但是被设置标记后最后一行和最
后一列有零了,无法判断这个零是否是本来就是零还是标记后才是零,也就无法得出最
后一行和最后一列元素的正确值。
因此,我觉得此方法不太对。。。
这道题不用extra space 真的有方法可以做吗?求指教 |
w***y 发帖数: 6251 | 4 我看到的解法是, 遍历到第一个有0的行列, 用这个相应的行/列, 来保存需要清零
的行/列---不知道说清楚了没有, 反正这个行/列最后都是要清零的,值修改了
也没关系的,用完了最后清零这部分 |
c**********e 发帖数: 58 | 5 说的听清楚的,感觉你这个解法是对的。
Thanks
【在 w***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我看到的解法是, 遍历到第一个有0的行列, 用这个相应的行/列, 来保存需要清零 : 的行/列---不知道说清楚了没有, 反正这个行/列最后都是要清零的,值修改了 : 也没关系的,用完了最后清零这部分
|
d******e 发帖数: 2265 | 6 你可以先处理第一行和第一列,如果有零,m[0][0] = 0;剩下的不变。
矩阵剩下的projected to 第一行和第一列
if (m[i][j] ==0)
{ m[0][j] =0; m[i][0] = 0; }
然后你真正填零的时候,倒着从n-1 到 0来遍历你的两个array.
然后所有的都不变,复杂度也不变。
【在 p****3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 【 以下文字转载自 Programming 讨论区 】 : 发信人: pv3633 (pv3633), 信区: Programming : 标 题: 求教矩阵改零的问题 : 发信站: BBS 未名空间站 (Sat May 25 12:04:34 2013, 美东) : 就是遇到零就要行列都改成零的那题 : 只遍历一次,不用额外空间 : 我的想法是 : 遍历一次但是不包括最后一行最后一列 : 遇到[ij]为零时在最后一行最后一列做记号 : 最后遍历最后行和列把整行和列改成零
|
r*********n 发帖数: 4553 | |
r*****s 发帖数: 74 | 8 public void setZeroes(int[][] matrix) {
// Start typing your Java solution below
// DO NOT write main() function
boolean xZero = false, yZero = false;
int m = matrix.length, n = matrix[0].length;
// record first row.
for (int i = 0; i < n; i ++){
if (matrix[0][i] == 0){
xZero = true;
break;
}
}
// record first column.
for (int j = 0; j < m; j ++){
if (matrix[j][0] == 0){
yZero = true;
break;
}
}
// bubble each zero element
for (int i = 1; i < m; i++){
for (int j = 1; j < n; j++){
if (matrix[i][j] == 0){
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// Row-wise.
for (int i = 1; i < m; i ++){
if (matrix[i][0] == 0){
for (int j = 1; j < n; j ++){
matrix[i][j] = 0;
}
}
}
// Column-wise.
for (int j = 1; j < n; j ++){
if (matrix[0][j] == 0){
for (int i = 1; i < m; i++){
matrix[i][j] = 0;
}
}
}
if (xZero){
for (int j = 0; j < n; j++){
matrix[0][j] = 0;
}
}
if (yZero){
for (int i = 0; i < m; i ++){
matrix[i][0] = 0;
}
}
} |
M*******u 发帖数: 51 | 9 Space extra 1) O(N^2) 另开一个matrix 来存放有0的element 2) O(2N) 两个数组
存放有0的i和j
3) O(1) 第一个0的行和列存放将来有0的i和j
【在 w***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我看到的解法是, 遍历到第一个有0的行列, 用这个相应的行/列, 来保存需要清零 : 的行/列---不知道说清楚了没有, 反正这个行/列最后都是要清零的,值修改了 : 也没关系的,用完了最后清零这部分
|