Set Matrix Zeroes

Q: Какова временная сложность алгоритма обнуления матрицы?

O(m·n) для матрицы m × n , поскольку каждая ячейка считывается и записывается постоянное число раз. Ни одно решение не работает быстрее, поскольку любая пропущенная ячейка могла бы содержать 0, меняющий ответ. Дополнительная память составляет O(m + n) при использовании массивов-маркеров и O(1) при использовании первой строки и первого столбца в качестве маркеров.

СреднеМассивы и строки Хеширование

+10

На вход подаётся сетка целых чисел размером m × n, заданная построчно, так что matrix[i][j] находится в строке i и столбце j. Везде, где в сетке стоит 0, установите 0 во всей этой строке и во всём этом столбце. Учитывайте только нули, присутствовавшие в начале: ячейка, которую вы замените на 0, не обнуляет свою строку или столбец. Вы можете изменить сетку на месте; верните её.

Функция

setZeroes(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: сетка целых чисел, по одному внутреннему списку на строку
Возвращаетinteger-2d-array: матрица, в которой все строки и все столбцы, содержащие 0, заменены на 0

Ограничения

m == matrix.length и n == matrix[i].length
1 ≤ m, n ≤ 1000 и m × n ≤ 5000
Все строки m содержат n значений.
-1000 ≤ matrix[i][j] ≤ 1000

Примеры

Ввод: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
Вывод: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
Пояснение: Единственный 0 находится в строке 1, столбце 1. Строка 1 становится полностью нулевой, как и столбец 1, поэтому 8 и 6 превращаются в 0. Четыре угловых элемента не находятся ни в одной из этих линий и сохраняют свои значения.

Дополнительный вопрос

В приведённом ниже способе используются две дополнительные булевы переменные. Можно ли обойтись одной, используя matrix[0][0] для обозначения первой строки?

Решение

Написанный вами 0 выглядит точно так же, как полученный 0, поэтому очистка строк во время сканирования распространяет нули по всей матрице. Разделите чтение и запись: сначала запишите, в каких строках и столбцах был 0, а затем очистите их. Храните эту информацию в двух массивах или, чтобы использовать O(1) дополнительной памяти, в первой строке и первом столбце самой матрицы.

Отметьте строки и столбцы в двух массивах

Идея

Ячейка в итоге становится 0 в точности тогда, когда в её строке или столбце изначально был 0. Поэтому за один проход, который ничего не записывает, сохрани факты в двух списках: zeroRow[i] и zeroCol[j], а затем обнули все ячейки, строка или столбец которых помечены. Ничего не распространяется, потому что все чтение выполняется до первой записи.

За каждый проход посещаются все m·n ячеек по одному разу, поэтому временная сложность составляет O(m·n), а массивы содержат m + n булевых значений.

Алгоритм

Создай zeroRow с m элементами и zeroCol с n элементами, все со значением false.
Просмотри каждую ячейку. Если matrix[i][j] равно 0, установи для zeroRow[i] и zeroCol[j] значение true.
Снова просмотри каждую ячейку и установи для неё значение 0, если zeroRow[i] или zeroCol[j] равно true.
Верни матрицу.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    zero_row = [False] * m
    zero_col = [False] * n
    # Pass 1: only read, so a new zero can never spread further.
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                zero_row[i] = True
                zero_col[j] = True
    # Pass 2: write.
    for i in range(m):
        for j in range(n):
            if zero_row[i] or zero_col[j]:
                matrix[i][j] = 0
    return matrix

Используйте первую строку и первый столбец в качестве маркеров

Идея

В первом столбце по одной ячейке на каждую строку, а в первой строке — по одной на каждый столбец: таковы размеры двух массивов-маркеров. Поэтому 0 в строке i, столбце j записывает 0 в matrix[i][0] и matrix[0][j]. Ничего не теряется: каждая из этих ячеек находится в строке или столбце, которые в любом случае должны стать нулевыми.

Строка 0 и столбец 0 — это и данные, и маркеры, а маркер в них скрывает, содержали ли они собственный 0. Поэтому сначала проверь их и сохрани результаты в двух логических переменных. Отмечай и заполняй только ячейки с i ≥ 1 и j ≥ 1, а строку 0 и столбец 0 очищай в последнюю очередь, потому что при заполнении они считываются.

Во втором примере 3 в строке 1, столбце 1 сохраняется, потому что его маркеры — matrix[1][0] = 9 и matrix[0][1] = 4 — не равны 0. Время выполнения остаётся O(m·n), а дополнительная память — две логические переменные (O(m·n) в R, где сначала копируется входная матрица).

Алгоритм

Установи firstRowZero, если в строке 0 есть 0, и firstColZero, если в столбце 0 есть 0.
Для каждой ячейки с i ≥ 1 и j ≥ 1, в которой находится 0, установи matrix[i][0] и matrix[0][j] в 0.
Для каждой ячейки с i ≥ 1 и j ≥ 1 установи значение 0, если matrix[i][0] или matrix[0][j] равно 0.
Если firstRowZero, установи все значения в строке 0 в 0. Если firstColZero, установи все значения в столбце 0 в 0.
Верни матрицу.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    # The first row and column will hold the markers, so remember first
    # whether they need to become zero themselves.
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    # Mark: a zero inside the matrix flags its row in column 0
    # and its column in row 0.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    # Fill the inside from the markers.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    # The marker row and column go last.
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0
    return matrix

Ловушки и крайние случаи

Очищать строку и столбец сразу после обнаружения 0. В первом примере новый 0 в строке 1, столбце 2 затем очищает столбец 2, и сохраняется только 3 в верхнем левом углу.
Позволять matrix[0][0] отмечать и строку 0, и столбец 0. В [[1, 2, 3], [0, 5, 6], [7, 8, 9]] 0 в столбце 0 затем ошибочно очищает строку 0.
Очищать строку 0 или столбец 0 перед заполнением. В [[0, 2, 3], [4, 5, 6], [7, 8, 9]] тогда каждый столбец выглядит отмеченным, и вся матрица становится равной 0.
Забывать об отдельных строках. Если строка одна, циклы, начинающиеся с 1, ничего не делают, и всю работу выполняют логические значения: [[1, 0, 3]] должно превратиться в [[0, 0, 0]].

Частые вопросы3

Почему нельзя устанавливать нули во время обхода матрицы?

Написанный тобой 0 выглядит так же, как исходный 0. Когда сканирование доходит до него, он очищает свою строку и столбец, и эти новые нули распространяются дальше. Запиши все исходные нули, прежде чем менять любую ячейку.

Какова временная сложность алгоритма обнуления матрицы?

O(m·n) для матрицы m × n, поскольку каждая ячейка считывается и записывается постоянное число раз. Ни одно решение не работает быстрее, поскольку любая пропущенная ячейка могла бы содержать 0, меняющий ответ. Дополнительная память составляет O(m + n) при использовании массивов-маркеров и O(1) при использовании первой строки и первого столбца в качестве маркеров.

Можно ли помечать ячейки специальным значением вместо 0?

В некоторых решениях в ячейки, которые нужно очистить, записывают заполнитель, а в конце заменяют заполнители нулями. Это работает, только если заполнитель никогда не может встретиться во входных данных, чего для целочисленной матрицы редко можно гарантировать. Запись заполнителя во всю строку и весь столбец для каждого 0 также требует времени O(m·n·(m + n)).

def setZeroes(matrix):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]

Ожидаемый вывод

[[3, 0, 1], [0, 0, 0], [2, 0, 4]]