给定一个大小为 nxm 的矩阵，其中填充了 0 和 1
例如：
1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0
如果矩阵在 (i,j) 处为 1，则用 1 填充第 j 列和第 i 行
即，我们得到：
1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
所需复杂度：O(n*m) 时间和 O(1) 空间
注意：您不能在矩阵条目中存储除“0”或“1”之外的任何内容
以上是微软面试题。
我想了两个小时。我有一些线索，但不能再继续了。
行。这个问题的第一个重要部分是Even using a straight forward brute-force way，它不容易解决。
如果我只使用两个循环遍历矩阵中的每个单元格，并更改相应的行和列，则无法完成，因为生成的矩阵应基于原点矩阵。
例如，如果我看到a[0][0] == 1，我不能全部更改为row 0，因为那会影响as本来没有 0。column 01row 1row 1
我注意到的第二件事是，如果一行r只包含0而一列c只包含0，那么a[r][c]一定是0；对于不在此模式中的任何其他位置应该是1。
然后另一个问题来了，如果我找到这样的行和列，我怎样才能将相应的单元格标记a[r][c]为special它已经是 0。
我的直觉是我应该对此使用某种位操作。或者为了满足所需的复杂性，我必须做类似After I take care of a[i][j], I should then proceed to deal with a[i+1][j+1], instead of scan row by row or column by column.
即使对于不考虑时间复杂度的蛮力，我也无法用其他条件解决它。
有人有线索吗？
解决方案：Java版
@japreiss 已经回答了这个问题，他/她的回答是聪明而正确的。他的代码是 Python 的，现在我给出 Java 版本。学分都去@japreiss
public class MatrixTransformer {
private int[][] a;
private int m;
private int n;
public MatrixTransformer(int[][] _a, int _m, int _n) {
a = _a;
m = _m;
n = _n;
}
private int scanRow(int i) {
int allZero = 0;
for(int k = 0;k < n;k++)
if (a[i][k] == 1) {
allZero = 1;
break;
}
return allZero;
}
private int scanColumn(int j) {
int allZero = 0;
for(int k = 0;k < m;k++)
if (a[k][j] == 1) {
allZero = 1;
break;
}
return allZero;
}
private void setRowToAllOnes(int i) {
for(int k = 0; k < n;k++)
a[i][k] = 1;
}
private void setColToAllOnes(int j) {
for(int k = 0; k < m;k++)
a[k][j] = 1;
}
// # we're going to use the first row and column
// # of the matrix to store row and column scan values,
// # but we need aux storage to deal with the overlap
// firstRow = scanRow(0)
// firstCol = scanCol(0)
//
// # scan each column and store result in 1st row - O(mn) work
public void transform() {
int firstRow = scanRow(0);
int firstCol = scanColumn(0);
for(int k = 0;k < n;k++) {
a[0][k] = scanColumn(k);
}
// now row 0 tells us whether each column is all zeroes or not
// it's also the correct output unless row 0 contained a 1 originally
for(int k = 0;k < m;k++) {
a[k][0] = scanRow(k);
}
a[0][0] = firstCol | firstRow;
for (int i = 1;i < m;i++)
for(int j = 1;j < n;j++)
a[i][j] = a[0][j] | a[i][0];
if (firstRow == 1) {
setRowToAllOnes(0);
}
if (firstCol == 1)
setColToAllOnes(0);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i< m;i++) {
for(int j = 0;j < n;j++) {
sb.append(a[i][j] + ", ");
}
sb.append("\n");
}
return sb.toString();
}
/**
* @param args
*/
public static void main(String[] args) {
int[][] a = {{1, 1, 0, 1, 0}, {0, 0, 0, 0, 0},{0, 1, 0, 0, 0},{1, 0, 1, 1, 0}};
MatrixTransformer mt = new MatrixTransformer(a, 4, 5);
mt.transform();
System.out.println(mt);
}
}