Microsoft Interview: преобразование матрицы

Дана матрица размера nxm, заполненная нулями и единицами

, например:

1 1 0 1 0

0 0 0 0 0

0 1 0 0 0

1 0 1 1 0

если матрица имеет 1 в (i,j), заполните столбец 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» в элементах матрицы.

Выше приведен вопрос для интервью Microsoft.

Я думал уже два часа. У меня есть некоторые подсказки, но я больше не могу продолжать.

Хорошо. Первая важная часть этого вопроса заключается в том, что Даже используя прямой метод грубой силы, его нелегко решить.

Если я просто использую два цикла для перебора каждой ячейки в матрице и изменяю соответствующие строку и столбец, это невозможно сделать, поскольку результирующая матрица должна быть основана на исходной матрице.

Например, если я вижу a[0][0] == 1, я не могу изменить строку 0и столбец 0на 1, потому что это повлияет на строку 1, поскольку строка 1изначально не имеет 0.

Второе, что я заметил, это то, что если строка rсодержит только 0, а столбец cсодержит только 0, то a[r][c]должно быть 0; для любой другой позиции, которая не находится в этом шаблоне, должно быть 1.

Тогда возникает другой вопрос: если я найду такую ​​строку и столбец, как я могу пометить соответствующую ячейку a[r][c]как special, поскольку она уже равна 0

Моя интуиция подсказывает, что я должен использовать для этого какие-то битовые операции. Или, чтобы соответствовать требуемой сложности, я должен сделать что-то вроде После того, как я позабочусь о [i][j], я должен затем перейти к работе с [i+1][j+1] вместо сканировать строку за строкой или столбец за столбцом.

Даже для грубой силы без учета временной сложности я не могу решить ее с другими условиями.

Кто-нибудь знает?

Решение: версия 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);
    }

}