0 と 1 で満たされたサイズ nxm の行列が与えられた場合
例えば：
1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0
行列の (i,j) に 1 がある場合、列 j と行 i を 1 で埋めます
つまり、次のようになります。
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」以外を格納することはできません
上記は、マイクロソフト インタビューの質問です。
ここで2時間考えました。手がかりはあるが、これ以上先に進めない。
Ok。この問題の最初の重要な部分は、Even using a straight forward brute-force way簡単には解決できないということです。
2 つのループを使用してマトリックス内のすべてのセルを反復処理し、それに応じて行と列を変更すると、結果のマトリックスは元のマトリックスに基づく必要があるため、実行できません。
たとえば、 が表示されている場合、すべてをにa[0][0] == 1変更することはできません。これは、 には元々 0 がないため影響します。row 0column 01row 1row 1
2 番目に気付いたのは、行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);
}
}