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 的大作中提到】
: 我看到的解法是， 遍历到第一个有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 的大作中提到】
: 【 以下文字转载自 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 的大作中提到】
: 我看到的解法是， 遍历到第一个有0的行列， 用这个相应的行／列， 来保存需要清零
: 的行／列－－－不知道说清楚了没有， 反正这个行／列最后都是要清零的，值修改了
: 也没关系的，用完了最后清零这部分
|
