求教矩阵改零的问题 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

求教矩阵改零的问题 (转载)

求教矩阵改零的问题 (转载)# JobHunting - 待字闺中

p*32013-05-25 07:05

1 楼

【以下文字转载自 Programming 讨论区】
发信人: pv3633 (pv3633), 信区: Programming
标题: 求教矩阵改零的问题
发信站: BBS 未名空间站 (Sat May 25 12:04:34 2013, 美东)
就是遇到零就要行列都改成零的那题
只遍历一次，不用额外空间
我的想法是
遍历一次但是不包括最后一行最后一列
遇到[ij]为零时在最后一行最后一列做记号
最后遍历最后行和列把整行和列改成零
但最后一步是否使时间上大于O(n^2)

b*g2013-05-25 07:05

2 楼

我也只想到了你这个做法，同问不用辅助空间的做法。
另外你这个做法还是o(n~2)的，这个不怕

c*e2013-05-25 07:05

3 楼

这样的话，如何判断最后一行和最后一列的每个元素是否为零呢？如果先遍历最后一行
和最后一列，只要行和列中各有一个元素为零，最后一行和列就全为零了。如果先遍历
其他的行和列，假设本来最后一行和最后一列全是1，但是被设置标记后最后一行和最
后一列有零了，无法判断这个零是否是本来就是零还是标记后才是零，也就无法得出最
后一行和最后一列元素的正确值。
因此，我觉得此方法不太对。。。
这道题不用extra space 真的有方法可以做吗？求指教

w*y2013-05-25 07:05

4 楼

我看到的解法是，遍历到第一个有0的行列，用这个相应的行／列，来保存需要清零
的行／列－－－不知道说清楚了没有，反正这个行／列最后都是要清零的，值修改了
也没关系的，用完了最后清零这部分

c*e2013-05-25 07:05

5 楼

说的听清楚的，感觉你这个解法是对的。
Thanks

【在 w***y 的大作中提到】

: 我看到的解法是，遍历到第一个有0的行列，用这个相应的行／列，来保存需要清零
: 的行／列－－－不知道说清楚了没有，反正这个行／列最后都是要清零的，值修改了
: 也没关系的，用完了最后清零这部分

d*e2013-05-25 07:05

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 的大作中提到】

: 【以下文字转载自 Programming 讨论区】
: 发信人: pv3633 (pv3633), 信区: Programming
: 标题: 求教矩阵改零的问题
: 发信站: BBS 未名空间站 (Sat May 25 12:04:34 2013, 美东)
: 就是遇到零就要行列都改成零的那题
: 只遍历一次，不用额外空间
: 我的想法是
: 遍历一次但是不包括最后一行最后一列
: 遇到[ij]为零时在最后一行最后一列做记号
: 最后遍历最后行和列把整行和列改成零

r*n2013-05-25 07:05

7 楼

谁能把完整的题目发出来？
thx

r*s2013-05-25 07:05

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;
}
}

}