给定大小为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，则在列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”以外的任何内容

上面是一个Microsoft面试问题。

我想了两个小时。我有一些线索，但无法继续进行。

好。这个问题的第一个重要部分是Even using a straight forward brute-force way，它很难解决。

如果我仅使用两个循环来遍历矩阵中的每个单元格，并更改相应的行和列，则无法完成，因为结果矩阵应基于原始矩阵。

例如，如果我看到a[0][0] == 1，我不能改变row 0和column 0所有1，因为这会影响到row 1作为row 1不具有0最初。

我注意到的第二件事是，如果一行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);
    }

}