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

Учитывая матрицу размера n x m, заполненную 0 и 1

например:.

1 1 0 1 0

0 0 0 0 0

0 1 0 0 0

1 0 1 1 0

если матрица имеет 1 at (i, j), заполните столбец j и строку я 1

i.e., получим:

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.

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

Ok. Первая важная часть этого вопроса заключается в том, что 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 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);
    }

}

Ответ 1

Вот решение в псевдокоде python, в котором используется 2 дополнительных bool хранилища. Я думаю, что это более ясно, чем я мог сделать на английском языке.

def scanRow(i):
    return 0 if row i is all zeroes, else 1

def scanColumn(j):
    return 0 if col j is all zeroes, else 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
for col in range(1, n):
    matrix[0, col] = scanColumn(col)

# now row 0 tells us whether each column is all zeroes or not
# it also the correct output unless row 0 contained a 1 originally

# do the same for rows into column 0 - O(mn) work
for row in range(1, m):
    matrix[row, 0] = scanRow(row)

matrix[0,0] = firstRow or firstCol

# now deal with the rest of the values - O(mn) work
for row in range(1, m):
    for col in range(1, n):
        matrix[row, col] = matrix[0, col] or matrix[row, 0]


# 3 O(mn) passes!

# go back and fix row 0 and column 0
if firstRow:
    # set row 0 to all ones

if firstCol:
    # set col 0 to all ones

Ответ 2

Вот еще одна интуиция, которая дает чистый и простой алгоритм для решения проблемы.

Исходный алгоритм с использованием пространства O (n).

В настоящее время пусть игнорирует ограничение памяти O (1). Предположим, что вы можете использовать память O (n) (если матрица равна m & times; n). Это значительно облегчило бы эту проблему, и мы могли бы использовать следующую стратегию:

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

В качестве примера рассмотрим этот массив:

Мы начнем с создания и заполнения вспомогательного массива, который можно выполнить за время O (mn), посетив каждый столбец по одному за раз. Это показано здесь:

1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0

1 1 1 1 0  <--- aux array

Затем мы перебираем строки и заполняем их, если они содержат все 1. Это дает следующий результат:

1 1 1 1 1
0 0 0 0 0
1 1 1 1 1
1 1 1 1 1

1 1 1 1 0  <--- aux array

Наконец, мы заполняем каждый столбец 1, если вспомогательный массив имеет 1 в этой позиции. Это показано здесь:

1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1

1 1 1 1 0  <--- aux array

Итак, есть одна проблема: это использует O (n) пространство, которого у нас нет! Итак, зачем даже идти по этому маршруту?

Пересмотренный алгоритм с использованием пространства O (1).

Оказывается, мы можем использовать очень симпатичный трюк для запуска этого алгоритма с использованием пространства O (1). Нам нужно провести ключевое наблюдение: если каждая строка содержит хотя бы одну единицу, то вся матрица становится равной 1. Поэтому мы начинаем, если это так. Если это так, здорово! Мы закончили.

В противном случае в матрице должна быть какая-то строка, содержащая все 0. Поскольку эта строка - все 0, мы знаем, что в "заполнении каждой строки, содержащей шаг 1 с 1", строка не будет заполнена. Поэтому мы можем использовать эту строку в качестве нашего вспомогательного массива!

Посмотрите на это в действии. Начните с этого:

Теперь мы можем найти строку со всеми 0 в ней и использовать ее в качестве нашего вспомогательного массива:

1 1 0 1 0
0 0 0 0 0  <-- Aux array
0 1 0 0 0
1 0 1 1 0

Теперь мы заполняем вспомогательный массив, просматривая каждый столбец и отмечая, какие из них содержат по крайней мере один 1:

1 1 0 1 0
1 1 1 1 0  <-- Aux array
0 1 0 0 0
1 0 1 1 0

Совершенно безопасно заполнить 1 здесь, потому что мы знаем, что они все равно будут заполнены. Теперь для каждой строки, содержащей 1, кроме строки вспомогательного массива, мы заполняем эти строки с помощью 1:

1 1 1 1 1
1 1 1 1 0  <-- Aux array
1 1 1 1 1
1 1 1 1 1

Мы пропускаем вспомогательный массив, потому что изначально это все 0, поэтому он обычно не заполняется. Наконец, мы заполняем каждый столбец 1 во вспомогательном массиве с 1, давая этот окончательный результат:

1 1 1 1 1
1 1 1 1 0  <-- Aux array
1 1 1 1 1 
1 1 1 1 1

Сделайте еще один пример. Рассмотрим эту настройку:

Сначала мы найдем строку, в которой все нули, как показано ниже:

1 0 0 0
0 0 1 0
0 0 0 0 <-- Aux array
0 0 1 0

Затем добавьте эту строку, пометив столбцы, содержащие 1:

1 0 0 0
0 0 1 0
1 0 1 0 <-- Aux array
0 0 1 0

Теперь заполните все строки, содержащие 1:

1 1 1 1
1 1 1 1
1 0 1 0 <-- Aux array
1 1 1 1

Затем заполните все столбцы, содержащие 1 в массиве aux с 1. Это уже сделано здесь, и у нас есть наш результат!

В качестве другого примера рассмотрим этот массив:

1 0 0
0 0 1
0 1 0

Каждая строка содержит хотя бы один символ 1, поэтому мы просто заполняем матрицу единицами и выполняем.

Наконец, попробуйте этот пример:

У нас есть много вариантов для массивов aux, поэтому давайте выбрать первую строку:

0 0 0 0 0 <-- aux array
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 1 0

Теперь мы заполняем массив aux:

0 1 0 1 0 <-- aux array
0 0 0 0 0 
0 1 0 0 0
0 0 0 0 0
0 0 0 1 0

Теперь мы заполняем строки:

0 1 0 1 0 <-- aux array
0 0 0 0 0 
1 1 1 1 1
0 0 0 0 0
1 1 1 1 1

Теперь мы заполняем столбцы на основе массива aux:

0 1 0 1 0 <-- aux array
0 1 0 1 0 
1 1 1 1 1
0 1 0 1 0
1 1 1 1 1

И все готово! Все это работает в O (mn) времени, потому что мы

Do O (mn) работают, чтобы найти массив aux и, возможно, O (mn) работают немедленно, если его не существует.
Do O (mn) работают, чтобы заполнить массив aux.
Do O (mn) работают, чтобы заполнить строки, содержащие 1s.
Do O (mn) работают для заполнения столбцов, содержащих 1s.

Кроме того, он использует только пространство O (1), так как нам просто нужно сохранить индекс массива aux и достаточно переменных для выполнения циклов над матрицей.

EDIT: у меня есть реализация Java этого алгоритма с комментариями, описывающими это подробно на моем личном сайте. Наслаждайтесь!

Надеюсь, это поможет!

Ответ 3

Предполагаемая матрица основана на 0, т.е. первый элемент находится на мат [0] [0]

Используйте первую строку и первый столбец в качестве заголовков таблиц, чтобы содержать информацию о столбцах и строках соответственно. 1.1 Обратите внимание на элемент на мат [0] [0]. Если оно равно 1, оно потребует специальной обработки в конце (описано ниже)
Теперь начните сканирование внутренней матрицы с индекса [1] [1] до последнего элемента 2.1 Если элемент в [row] [col] == 1 затем обновляет данные заголовка таблицы следующим образом Строка: мат [строка] [0] = 1; Колонка: мат [0] [col] = 1;

На этом этапе у нас есть полная информация о том, какой столбец и строка должны быть установлены в 1

Снова начните сканирование внутренней матрицы, начиная с мата [1] [1], и установите каждый элемент до 1, если либо текущая строка, либо столбец содержит 1 в заголовке таблицы: if ((mat [row] [0] == 1) || (mat [0] [col] == 1)) затем установите mat [row] [col] в 1..

В этот момент мы обработали все ячейки во внутренней матрице, и мы но для обработки самого заголовка таблицы

Обработать заголовок таблицы Если матовый [0] [0] == 1 затем задает все элементы в первом столбце и первый строка до 1
Готово

Сложность времени O (2 * ((n-1) (m-1) + (n + m-1)), т.е. O (2 * n * m - (n + m) + 1), т.е. O (2 * п * м) Пространство O (1)

Смотрите мою реализацию на http://codepad.org/fycIyflw

Ответ 4

Другим решением было бы сканирование матрицы, как обычно, и в первом 1 вы разделили матрицу на 4 квадранта. Затем вы устанавливаете строку и столбец в 1 и рекурсивно обрабатываете каждый квадрант. Просто убедитесь, что вы установите все столбцы и строки, даже если вы сканируете только квадрант.

Ответ 5

public void setOnes(int [][] matrix){

    boolean [] row = new boolean [matrix.length]
    boolean [] col = new boolean [matrix[0].length]
    for (int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[0].length;j++){
            if (matrix[i][j] == 1){
                row[i] = true
                col[j] = true
            }
        }
    }

    for (int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[0].length;j++){
            if (row[i] || col[j]){
                matrix[i][j] = 1;
            }
        }
    }
}