Set Matrix Zeroes

Q: Wie hoch ist die Zeitkomplexität von Set Matrix Zeroes?

O(m·n) für eine m × n -Matrix, da jede Zelle eine konstante Anzahl von Malen gelesen und beschrieben wird. Keine Lösung ist effizienter, denn jede übersprungene Zelle könnte die 0 enthalten, die das Ergebnis verändert. Der zusätzliche Speicherbedarf beträgt O(m + n) mit Markierungsarrays und O(1), wenn die erste Zeile und Spalte als Markierungen verwendet werden.

MittelArrays und Strings Hashing

+10

Die Eingabe ist ein m × n-Raster aus Ganzzahlen, das zeilenweise angegeben wird, sodass sich matrix[i][j] in Zeile i und Spalte j befindet. Überall dort, wo das Raster eine 0 enthält, setze die gesamte Zeile und die gesamte Spalte auf 0. Es zählen nur die Nullen, die zu Beginn vorhanden sind: Eine Zelle, die du auf 0 setzt, setzt nicht ihre eigene Zeile oder Spalte auf 0. Du darfst das Raster direkt verändern; gib es zurück.

Funktion

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

matrixinteger-2d-array: das Raster aus Ganzzahlen, eine innere Liste pro Zeile
Gibt zurückinteger-2d-array: die Matrix, bei der jede Zeile und jede Spalte, die eine 0 enthielt, auf 0 gesetzt wurde

Einschränkungen

m == matrix.length und n == matrix[i].length
1 ≤ m, n ≤ 1000 und m × n ≤ 5000
Alle Zeilen mit m enthalten n Werte.
-1000 ≤ matrix[i][j] ≤ 1000

Beispiele

Eingabe: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
Ausgabe: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
Erklärung: Die einzige 0 befindet sich in Zeile 1, Spalte 1. Zeile 1 besteht danach nur noch aus Nullen, ebenso Spalte 1, wodurch die 8 und die 6 zu 0 werden. Die vier Ecken liegen auf keiner der beiden Linien und behalten ihre Werte.

Weiterführende Frage

Der folgende Ansatz behält zwei zusätzliche boolesche Werte bei. Kommst du mit einem aus und lässt matrix[0][0] für die erste Zeile stehen?

Lösung

Eine 0, die du schreibst, sieht genauso aus wie eine 0, die bereits vorhanden war. Deshalb breiten sich beim Löschen von Zeilen während des Durchlaufs die Nullen über die Matrix aus. Trenne das Lesen vom Schreiben: Halte zuerst fest, welche Zeilen und Spalten eine 0 enthielten, und lösche sie anschließend. Speichere diese Information in zwei Arrays oder – für O(1) zusätzlichen Speicherplatz – in der ersten Zeile und Spalte der Matrix selbst.

Zeilen und Spalten in zwei Arrays markieren

Idee

Eine Zelle wird genau dann zu 0, wenn ihre Zeile oder ihre Spalte zu Beginn eine 0 enthielt. Halte daher zwei Listen mit Informationen fest, zeroRow[i] und zeroCol[j], und zwar in einem Durchlauf, der nichts schreibt. Setze anschließend jede Zelle auf 0, deren Zeile oder Spalte markiert ist. Es breitet sich nichts aus, da alle Lesevorgänge abgeschlossen sind, bevor der erste Schreibvorgang erfolgt.

Jeder Durchlauf besucht die m·n Zellen genau einmal, daher beträgt die Laufzeit O(m·n), und die Arrays enthalten m + n boolesche Werte.

Algorithmus

Erstelle zeroRow mit m Einträgen und zeroCol mit n Einträgen, alle auf false gesetzt.
Durchlaufe jede Zelle. Wenn matrix[i][j] 0 ist, setze zeroRow[i] und zeroCol[j] auf true.
Durchlaufe erneut jede Zelle und setze sie auf 0, wenn zeroRow[i] oder zeroCol[j] true ist.
Gib die Matrix zurück.

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

Verwende die erste Zeile und Spalte als Markierungen

Idee

Die erste Spalte hat eine Zelle pro Zeile und die erste Zeile eine pro Spalte – das entspricht der Form der beiden Markierungsarrays. Eine 0 in Zeile i, Spalte j schreibt also eine 0 in matrix[i][0] und matrix[0][j]. Dabei geht nichts verloren: Jede dieser Zellen liegt in einer Zeile oder Spalte, die ohnehin zu 0 werden muss.

Zeile 0 und Spalte 0 enthalten sowohl Daten als auch Markierungen, und eine Markierung dort verdeckt, ob sie selbst eine 0 enthielten. Prüfe sie deshalb zuerst und halte die Ergebnisse in zwei booleschen Variablen fest. Markiere und fülle nur Zellen mit i ≥ 1 und j ≥ 1, und setze Zeile 0 und Spalte 0 zuletzt auf 0, da der Füllvorgang ihre Werte liest.

Im zweiten Beispiel bleibt die 3 in Zeile 1, Spalte 1 erhalten, weil ihre Markierungen matrix[1][0] = 9 und matrix[0][1] = 4 nicht 0 sind. Die Laufzeit bleibt O(m·n), mit zwei booleschen Variablen zusätzlichem Speicher (in R O(m·n), da dort zuerst die Eingabe kopiert wird).

Algorithmus

Setze firstRowZero, wenn Zeile 0 eine 0 enthält, und firstColZero, wenn Spalte 0 eine 0 enthält.
Setze für jede Zelle mit i ≥ 1 und j ≥ 1, die den Wert 0 enthält, matrix[i][0] und matrix[0][j] auf 0.
Setze jede Zelle mit i ≥ 1 und j ≥ 1 auf 0, wenn matrix[i][0] oder matrix[0][j] 0 ist.
Wenn firstRowZero gesetzt ist, setze Zeile 0 auf 0. Wenn firstColZero gesetzt ist, setze Spalte 0 auf 0.
Gib die Matrix zurück.

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

Stolperfallen und Grenzfälle

Eine Zeile und eine Spalte leeren, sobald du eine 0 findest. Im ersten Beispiel leert die neue 0 in Zeile 1, Spalte 2 anschließend Spalte 2, und nur die 3 oben links bleibt erhalten.
matrix[0][0] sowohl Zeile 0 als auch Spalte 0 markieren lassen. In [[1, 2, 3], [0, 5, 6], [7, 8, 9]] leert die 0 in Spalte 0 dann fälschlicherweise Zeile 0.
Zeile 0 oder Spalte 0 vor dem Auffüllen leeren. In [[0, 2, 3], [4, 5, 6], [7, 8, 9]] sieht dann jede Spalte markiert aus, und die gesamte Matrix wird zu 0.
Einzelne Zeilen vergessen. Bei einer Zeile tun die Schleifen, die bei 1 beginnen, nichts, und die booleschen Werte übernehmen die ganze Arbeit: [[1, 0, 3]] muss zu [[0, 0, 0]] werden.

Häufige Fragen3

Warum kannst du die Nullen nicht setzen, während du die Matrix durchläufst?

Eine 0, die du einträgst, sieht genauso aus wie eine ursprüngliche 0. Wenn der Scan sie erreicht, löscht sie ihre eigene Zeile und Spalte, und diese neuen Nullen breiten sich weiter aus. Notiere jede ursprüngliche Null, bevor du eine Zelle änderst.

Wie hoch ist die Zeitkomplexität von Set Matrix Zeroes?

O(m·n) für eine m × n-Matrix, da jede Zelle eine konstante Anzahl von Malen gelesen und beschrieben wird. Keine Lösung ist effizienter, denn jede übersprungene Zelle könnte die 0 enthalten, die das Ergebnis verändert. Der zusätzliche Speicherbedarf beträgt O(m + n) mit Markierungsarrays und O(1), wenn die erste Zeile und Spalte als Markierungen verwendet werden.

Kannst du Zellen mit einem speziellen Wert statt mit 0 markieren?

Manche Lösungen schreiben einen Platzhalter in die Zellen, die geleert werden sollen, und wandeln die Platzhalter am Ende in Nullen um. Das funktioniert nur, wenn der Platzhalter niemals in der Eingabe vorkommen kann, was eine ganzzahlige Matrix selten garantiert. Ihn für jede 0 entlang einer Zeile und einer Spalte einzutragen, kostet außerdem O(m·n·(m + n)) Zeit.

def setZeroes(matrix):
    # Schreibe hier den Code

Test #1

Test #2

Argument

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

Erwartete Ausgabe

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