Set Matrix Zeroes

Q: Jaka jest złożoność czasowa problemu „Set Matrix Zeroes”?

O(m·n) dla macierzy m × n , ponieważ każda komórka jest odczytywana i zapisywana stałą liczbę razy. Żadne rozwiązanie nie jest wydajniejsze, ponieważ każda pominięta komórka mogłaby zawierać 0 zmieniające wynik. Dodatkowa przestrzeń wynosi O(m + n) przy użyciu tablic znaczników oraz O(1) przy użyciu pierwszego wiersza i kolumny jako znaczników.

ŚrednieTablice i napisy Haszowanie

+10

Dane wejściowe to siatka liczb całkowitych o wymiarach m × n, podana wierszami, więc matrix[i][j] znajduje się w wierszu i i kolumnie j. Wszędzie tam, gdzie siatka zawiera 0, ustaw cały wiersz i całą kolumnę na 0. Liczą się tylko zera obecne na początku: komórka, którą zmienisz na 0, nie wyzeruje swojego wiersza ani kolumny. Możesz modyfikować siatkę w miejscu; zwróć ją.

Funkcja

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

matrixinteger-2d-array: siatka liczb całkowitych, jedna lista wewnętrzna na wiersz
Zwracainteger-2d-array: macierz, w której każdy wiersz i każda kolumna zawierające 0 zostały ustawione na 0

Ograniczenia

m == matrix.length i n == matrix[i].length
1 ≤ m, n ≤ 1000 i m × n ≤ 5000
Wszystkie wiersze m zawierają n wartości.
-1000 ≤ matrix[i][j] ≤ 1000

Przykłady

Wejście: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
Wyjście: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
Wyjaśnienie: Jedyne 0 znajduje się w wierszu 1, kolumnie 1. Wiersz 1 składa się teraz z samych zer, podobnie jak kolumna 1, co zmienia 8 i 6 na 0. Cztery narożniki nie leżą na żadnej z tych linii, więc zachowują swoje wartości.

Pytanie dodatkowe

Najlepsze podejście poniżej przechowuje dwa dodatkowe booleany. Czy możesz obejść się z jednym, używając matrix[0][0] do oznaczenia pierwszego wiersza?

Rozwiązanie

Wpisane przez ciebie 0 wygląda dokładnie tak samo jak otrzymane 0, więc czyszczenie wierszy podczas skanowania rozprzestrzenia zera po macierzy. Oddziel odczyt od zapisu: najpierw zapisz, które wiersze i kolumny zawierały 0, a potem je wyczyść. Przechowuj te informacje w dwóch tablicach albo, aby uzyskać dodatkową przestrzeń O(1), w pierwszym wierszu i pierwszej kolumnie samej macierzy.

Oznacz wiersze i kolumny w dwóch tablicach

Intuicja

Komórka kończy z wartością 0 dokładnie wtedy, gdy na początku w jej wierszu lub kolumnie znajdowało się 0. Zapisz więc dwa zestawy informacji, zeroRow[i] i zeroCol[j], podczas przebiegu, który niczego nie zapisuje, a następnie wyzeruj każdą komórkę, której wiersz lub kolumna jest oznaczona. Nic się nie rozprzestrzenia, ponieważ wszystkie odczyty są wykonywane przed pierwszym zapisem.

Każdy przebieg odwiedza m·n komórek raz, więc czas wynosi O(m·n), a tablice przechowują m + n wartości logicznych.

Algorytm

Utwórz zeroRow z m wpisami i zeroCol z n wpisami, wszystkie ustawione na false.
Przejdź przez każdą komórkę. Gdy matrix[i][j] ma wartość 0, ustaw zeroRow[i] i zeroCol[j] na true.
Ponownie przejdź przez każdą komórkę i ustaw jej wartość na 0, gdy zeroRow[i] lub zeroCol[j] ma wartość true.
Zwróć macierz.

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

Użyj pierwszego wiersza i pierwszej kolumny jako znaczników

Intuicja

Pierwsza kolumna ma jedną komórkę na każdy wiersz, a pierwszy wiersz — jedną na każdą kolumnę: takie są rozmiary dwóch tablic znaczników. Zatem 0 w wierszu i, kolumnie j zapisuje 0 w matrix[i][0] i matrix[0][j]. Niczego to nie traci: każda z tych komórek leży w wierszu lub kolumnie, które i tak muszą zostać wyzerowane.

Wiersz 0 i kolumna 0 zawierają zarówno dane, jak i znaczniki, a znacznik w tych miejscach przesłania informację, czy znajdowało się tam własne 0. Dlatego najpierw je sprawdź i zachowaj wyniki w dwóch wartościach logicznych. Oznaczaj i wypełniaj tylko komórki z i ≥ 1 i j ≥ 1, a wiersz 0 i kolumnę 0 wyzeruj na końcu, ponieważ wypełnianie odczytuje z nich dane.

W drugim przykładzie 3 w wierszu 1, kolumnie 1 pozostaje bez zmian, ponieważ jego znaczniki, matrix[1][0] = 9 i matrix[0][1] = 4, nie są równe 0. Złożoność czasowa pozostaje O(m·n), a dodatkowa pamięć ogranicza się do dwóch wartości logicznych (O(m·n) w R, które najpierw kopiuje dane wejściowe).

Algorytm

Ustaw firstRowZero, jeśli wiersz 0 zawiera 0, oraz firstColZero, jeśli kolumna 0 zawiera 0.
Dla każdej komórki z i ≥ 1 i j ≥ 1, która zawiera 0, ustaw matrix[i][0] i matrix[0][j] na 0.
Dla każdej komórki z i ≥ 1 i j ≥ 1 ustaw ją na 0, gdy matrix[i][0] lub matrix[0][j] wynosi 0.
Jeśli firstRowZero, ustaw wiersz 0 na 0. Jeśli firstColZero, ustaw kolumnę 0 na 0.
Zwróć macierz.

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

Pułapki i przypadki brzegowe

Czyszczenie wiersza i kolumny od razu po znalezieniu 0. W pierwszym przykładzie nowe 0 w wierszu 1, kolumnie 2 czyści następnie kolumnę 2, a przetrwa tylko 3 w lewym górnym rogu.
Pozwolenie, by matrix[0][0] oznaczało zarówno wiersz 0, jak i kolumnę 0. W [[1, 2, 3], [0, 5, 6], [7, 8, 9]] 0 w kolumnie 0 błędnie czyści wtedy wiersz 0.
Czyszczenie wiersza 0 lub kolumny 0 przed wypełnieniem. W [[0, 2, 3], [4, 5, 6], [7, 8, 9]] każda kolumna wygląda wtedy na oznaczoną, a cała macierz zmienia się w 0.
Zapominanie o pojedynczych wierszach. Przy jednym wierszu pętle rozpoczynające się od 1 nic nie robią, a całą pracę wykonują wartości logiczne: [[1, 0, 3]] musi zmienić się w [[0, 0, 0]].

Najczęstsze pytania3

Dlaczego nie możesz ustawiać zer podczas przeglądania macierzy?

Zapisane przez ciebie 0 wygląda tak samo jak oryginalne 0. Gdy skan do niego dotrze, wyczyści swój wiersz i kolumnę, a te nowe zera rozprzestrzenią się dalej. Zapisz pozycję każdego oryginalnego zera, zanim zmienisz jakąkolwiek komórkę.

Jaka jest złożoność czasowa problemu „Set Matrix Zeroes”?

O(m·n) dla macierzy m × n, ponieważ każda komórka jest odczytywana i zapisywana stałą liczbę razy. Żadne rozwiązanie nie jest wydajniejsze, ponieważ każda pominięta komórka mogłaby zawierać 0 zmieniające wynik. Dodatkowa przestrzeń wynosi O(m + n) przy użyciu tablic znaczników oraz O(1) przy użyciu pierwszego wiersza i kolumny jako znaczników.

Czy możesz oznaczać komórki specjalną wartością zamiast 0?

Niektóre rozwiązania wpisują do komórek przeznaczonych do wyczyszczenia wartość zastępczą, a na końcu zamieniają te wartości na zera. Działa to tylko wtedy, gdy wartość zastępcza nigdy nie występuje na wejściu, czego macierz liczb całkowitych rzadko gwarantuje. Wpisywanie jej wzdłuż wiersza i kolumny dla każdego 0 wymaga też czasu O(m·n·(m + n)).

def setZeroes(matrix):
    # Napisz kod tutaj

Test #1

Test #2

Argument

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

Oczekiwany wynik

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