Transpose Matrix

Q: Wie hoch ist die Zeitkomplexität beim Transponieren einer Matrix?

Es ist O(m × n) , weil jeder der m × n Werte einmal kopiert wird und nichts weniger erforderlich ist, um das Ergebnis zu erzeugen. Die neue Matrix benötigt O(m × n) Speicherplatz, was der Größe der Ausgabe selbst entspricht.

Q: Kannst du eine Matrix direkt transponieren?

Für eine quadratische Matrix, ja: Tausche matrix[i][j] für jede Zelle oberhalb der Diagonale mit matrix[j][i] , wobei du O(1) zusätzlichen Speicher verwendest. Bei einer nicht quadratischen Matrix hat das Ergebnis eine andere Form, daher benötigst du bei einer Liste von Zeilen eine neue Matrix.

Q: Wie transponiert man eine nichtquadratische Matrix?

Erstelle ein Ergebnis mit n Zeilen der Länge m , wobei die Eingabe m Zeilen der Länge n hat. Kopiere dann jeden Wert mit result[j][i] = matrix[i][j] . Die Idee der Diagonale aus dem quadratischen Fall trifft nicht zu, da die beiden Matrizen nicht dieselbe Form haben.

EinsteigerArrays und Strings

+10

Du erhältst eine Matrix aus Ganzzahlen als Liste von Zeilen: matrix[i][j] ist der Wert in Zeile i, Spalte j. Gib ihre Transponierte zurück, also die Matrix, die entsteht, wenn jede Zeile in eine Spalte umgewandelt wird. Der Wert in Zeile i, Spalte j wandert in Zeile j, Spalte i. Die Matrix muss nicht quadratisch sein: Eine m × n-Matrix wird zu einer n × m-Matrix.

Funktion

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

matrixinteger-2d-array: die m × n-Matrix als Liste aus m Zeilen mit jeweils n Ganzzahlen
Gibt zurückinteger-2d-array: die Transponierte einer n × m-Matrix als Liste mit n Zeilen aus jeweils m Ganzzahlen

Einschränkungen

1 ≤ m, n ≤ 1000, wobei m = matrix.length und n = matrix[i].length
m × n ≤ 5000
Jede Zeile hat dieselbe Länge n.
-1000 ≤ matrix[i][j] ≤ 1000

Beispiele

Eingabe: matrix = [[1, 2, 3], [4, 5, 6]]
Ausgabe: [[1, 4], [2, 5], [3, 6]]
Erklärung: Die erste Zeile [1, 2, 3] wird zur ersten Spalte und [4, 5, 6] zur zweiten. Liest man das Ergebnis zeilenweise, erhält man [1, 4], [2, 5], [3, 6]: Die 2 × 3-Matrix wurde in eine 3 × 2-Matrix umgewandelt.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Angenommen, die Matrix ist als ein einziges flaches Array aus m × n Werten gespeichert, Zeile für Zeile. Kannst du eine nicht quadratische Matrix innerhalb dieses Arrays transponieren, ohne ein zweites Array zu verwenden?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Das Transponieren ist eine reine Änderung der Adresse: Der Wert an (i, j) wandert nach (j, i), und es wird nichts berechnet. Die Aufgabe besteht darin, die Form richtig hinzubekommen. Eine nicht quadratische Matrix, die als Liste von Zeilen gespeichert ist, kann nicht an Ort und Stelle transponiert werden, da das Ergebnis n Zeilen der Länge m statt m Zeilen der Länge n hat. Deshalb erstellst du eine neue Matrix mit vertauschter Größe und füllst sie aus.

Lies die Matrix Spalte für Spalte.

Idee

Zeile j der Antwort ist Spalte j der Eingabe, von oben nach unten gelesen. Erstelle die Antwort also Zeile für Zeile: Sammle für jede Spalte j von 0 bis n-1 matrix[0][j], matrix[1][j] und so weiter bis hinunter zu matrix[m-1][j], und füge diese Liste als nächste Zeile hinzu.

Bei [[1, 2, 3], [4, 5, 6]] ergibt Spalte 0 der Reihe nach 1 und 4, Spalte 1 der Reihe nach 2 und 5, Spalte 2 der Reihe nach 3 und 6. Die Antwort lautet [[1, 4], [2, 5], [3, 6]] mit n = 3 Zeilen mit jeweils m = 2 Werten.

Jeder Wert wird einmal gelesen und einmal geschrieben, daher beträgt die Laufzeit O(m × n) und das Ergebnis benötigt O(m × n) Speicherplatz. Der Aufwand liegt im Zugriffsmuster: Beim Erstellen einer neuen Zeile wird auf jede Eingabezeile zugegriffen, wobei von Zeile zu Zeile gesprungen wird, statt eine Zeile entlangzulesen.

Algorithmus

Sei m die Anzahl der Zeilen und n die Länge einer Zeile.
Beginne für jede Spalte j von 0 bis n-1 mit einer leeren Liste.
Füge für jedes i von 0 bis m-1 matrix[i][j] zu ihr hinzu.
Füge die Liste als Zeile j zum Ergebnis hinzu und gib das Ergebnis nach der letzten Spalte zurück.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    result = []
    for j in range(n):
        # Column j, read top to bottom, becomes row j of the answer.
        column = []
        for i in range(m):
            column.append(matrix[i][j])
        result.append(column)
    return result

Fülle ein neues n × m-Raster, indem du jede Zelle spiegelst

Idee

Lege zuerst die Form fest und fülle sie dann. Die Antwort hat n Zeilen der Länge m, also erstelle dieses Raster gleich zu Beginn. Lies die Eingabe anschließend in ihrer natürlichen Reihenfolge, Zeile für Zeile und von links nach rechts, und setze jeden Wert an seine gespiegelte Position: result[j][i] = matrix[i][j].

Die Regel ist korrekt, weil Transponieren genau diesem Vertauschen der beiden Indizes entspricht. Im quadratischen Beispiel [[1, 2], [3, 4]] bleiben die 1 und die 4 auf der Diagonalen an ihrer Position, die 2 wandert von (0, 1) nach (1, 0) und die 3 von (1, 0) nach (0, 1). Das ergibt [[1, 3], [2, 4]].

Jeder der m × n Werte wird einmal kopiert, daher beträgt die Laufzeit O(m × n). Das neue Raster benötigt O(m × n) Speicherplatz, den die Ausgabe ohnehin braucht. Beim zeilenweisen Lesen der Eingabe wird der Speicher in der Reihenfolge durchlaufen, in der die Werte abgelegt sind, und jede Ergebniszeile wird einmal in ihrer endgültigen Größe erstellt.

Algorithmus

Sei m die Anzahl der Zeilen und n die Länge einer Zeile.
Erstelle result mit n Zeilen, die jeweils m Werte enthalten.
Setze für jede Zeile i und jede Spalte j der Eingabe result[j][i] = matrix[i][j].
Gib result zurück.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    # The answer has n rows of m values each.
    result = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            result[j][i] = matrix[i][j]
    return result

Stolperfallen und Grenzfälle

Fast jede falsche Antwort liegt an der Form, nicht an den Werten.

Das Ergebnis mit der ursprünglichen Form erstellen. Ein Ergebnis mit m Zeilen und n Spalten funktioniert nur bei quadratischen Eingaben; beim Beispiel mit 2 × 3 führt result[2][0] über das Ende hinaus. Das Ergebnis benötigt n Zeilen der Länge m.
Bei einer nicht quadratischen Matrix direkt in der Matrix tauschen. matrix[i][j] mit matrix[j][i] zu tauschen, funktioniert nur, wenn m = n, und selbst dann darf die Schleife nur die Zellen oberhalb der Diagonalen umfassen (j > i), sonst wird jedes Paar zweimal getauscht und die Matrix ist wieder unverändert.
Ein Zeilenobjekt gemeinsam nutzen. In Python erstellt [[0] * m] * n n Referenzen auf dieselbe Liste, sodass das Schreiben in eine Zelle die ganze Spalte beschreibt. Erstelle jede Zeile separat.
Die Spaltengrößen in C vergessen. Der Aufrufer liest *returnSize als Anzahl der Ergebniszeilen, n, und (*returnColumnSizes)[j] als Länge jeder Zeile, m.

Häufige Fragen4

Was ist die Transponierte einer Matrix?

Es ist die Matrix, die du erhältst, indem du Zeilen und Spalten vertauschst: Der Wert in Zeile i, Spalte j wandert in Zeile j, Spalte i. Eine 2 × 3-Matrix wird zu einer 3 × 2-Matrix, und zweimaliges Transponieren ergibt wieder die ursprüngliche Matrix.

Wie hoch ist die Zeitkomplexität beim Transponieren einer Matrix?

Es ist O(m × n), weil jeder der m × n Werte einmal kopiert wird und nichts weniger erforderlich ist, um das Ergebnis zu erzeugen. Die neue Matrix benötigt O(m × n) Speicherplatz, was der Größe der Ausgabe selbst entspricht.

Kannst du eine Matrix direkt transponieren?

Für eine quadratische Matrix, ja: Tausche matrix[i][j] für jede Zelle oberhalb der Diagonale mit matrix[j][i], wobei du O(1) zusätzlichen Speicher verwendest. Bei einer nicht quadratischen Matrix hat das Ergebnis eine andere Form, daher benötigst du bei einer Liste von Zeilen eine neue Matrix.

Wie transponiert man eine nichtquadratische Matrix?

Erstelle ein Ergebnis mit n Zeilen der Länge m, wobei die Eingabe m Zeilen der Länge n hat. Kopiere dann jeden Wert mit result[j][i] = matrix[i][j]. Die Idee der Diagonale aus dem quadratischen Fall trifft nicht zu, da die beiden Matrizen nicht dieselbe Form haben.

Python

def transpose(matrix):
    # Schreibe hier Code

Testfälle

Fall 1

Fall 2

Eingabe

matrix = [[1, 2, 3], [4, 5, 6]]

Erwartet

[[1, 4], [2, 5], [3, 6]]