给定一个如下所示的mxn矩阵:
1034
1234
3560
需要输出如下内容:
0000
1030
0000
*目标编号为0。
这是我的解决方案,但是我认为它不是非常有效(我认为空间和运行时间均为O(m ^ 2 * n)),并且想知道是否有更简单,更有效的方法来做到这一点。如果是,那是什么?
int[][] m = { { 1, 0, 3, 4 }, { 1, 2, 3, 4 }, { 3, 5, 6, 0 } };
m = zero(m, 0);
public static int[][] zero(int[][] m, int num) {
int rows = m.length;
int columns = m[0].length;
int [][] myInt = new int[rows][];
for(int i = 0; i < rows; i++){
myInt[i] = m[i].clone();
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (myInt[i][j] == num) {
m[i] = new int[columns];
for(int k = 0; k < rows; k++){
m[k][j] = 0;
}
break;
}
}
}
return m;
}
基本上,我首先克隆输入矩阵,然后遍历每一行并检查该行是否包含我的目标编号。如果是,则将原始矩阵中的整个行设置为零。然后,我执行另一个循环以将包含目标编号的列设置为零。我从一开始就克隆了矩阵,因此检查总是针对克隆的参考矩阵,而不是每次迭代都经过修改的矩阵。
最佳答案
我建议将BitSet用于行/列索引。
public static void zero(int[][] m, int num) {
int rows = m.length;
int columns = m[0].length;
BitSet rowsToClear = new BitSet(rows);
BitSet columnsToClear = new BitSet(columns);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (m[i][j] == num) {
rowsToClear.set(i);
columnsToClear.set(j);
}
}
}
for (int i = rowsToClear.nextSetBit(0); i >= 0;
i = rowsToClear.nextSetBit(i + 1)) {
Arrays.fill(m[i], 0);
}
for (int j = columnsToClear.nextSetBit(0); j >= 0;
j = columnsToClear.nextSetBit(j + 1)) {
for (int i = 0; i < rows; ++i) {
m[i][j] = 0;
}
}
//return m;
}