Transpose Matrix

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

O(m × n) : Jeder der m × n Werte wird einmal kopiert, und weniger ist nicht möglich, um das Ergebnis zu erzeugen. Die neue Matrix benötigt O(m × n) Speicherplatz, also so viel wie die Ausgabe selbst.

Q: Kannst du eine Matrix direkt transponieren?

Bei einer quadratischen Matrix: Ja. Vertausche matrix[i][j] mit matrix[j][i] für jede Zelle oberhalb der Diagonalen, mit O(1) zusätzlichem Speicher. Eine nicht quadratische Matrix ändert ihre Form, daher brauchst du bei einer Liste von Zeilen eine neue Matrix.

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: Der Wert in Zeile i, Spalte j wird in Zeile j, Spalte i verschoben, sodass jede Zeile zu einer Spalte wird. 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 n Ganzzahlen
Gibt zurückinteger-2d-array: die n × m-Transponierte, als Liste aus n Zeilen mit 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 Zeile [1, 2, 3] wird zur ersten Spalte und [4, 5, 6] zur zweiten. Zeilenweise gelesen lautet das Ergebnis [1, 4], [2, 5], [3, 6]: eine 3 × 2-Matrix.

Weiterführende Frage

Angenommen, die Matrix ist als ein 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?

Tipps

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

0 von 3 geöffnet

Lösung

Beim Transponieren wird nichts berechnet: Der Wert an (i, j) wandert zu (j, i). Die Arbeit besteht in der Form. Das Ergebnis hat n Zeilen mit der Länge m, daher kann eine nicht quadratische Liste von Zeilen nicht direkt transponiert werden; erstelle eine neue Matrix mit vertauschten Dimensionen und fülle sie.

Lies die Matrix spaltenweise

Idee

Zeile j der Antwort ist Spalte j der Eingabe, von oben nach unten gelesen. Für [[1, 2, 3], [4, 5, 6]] enthält Spalte 0 erst 1, dann 4, also ist die erste Zeile der Antwort [1, 4].

Jeder Wert wird einmal gelesen und einmal geschrieben: Laufzeit O(m × n) und O(m × n) Speicherplatz für das Ergebnis. Beim Erstellen jeder neuen Zeile springst du über jede Eingabezeile, statt eine Zeile entlangzugehen. Das ist die langsamere Art, den Speicher zu durchlaufen.

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 matrix[i][j] für jedes i von 0 bis m-1 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

Erstelle das n × m-Ergebnis vorab, lies dann die Eingabe in der gespeicherten Reihenfolge zeilenweise ein und setze jeden Wert an seine gespiegelte Adresse: result[j][i] = matrix[i][j]. Das ist korrekt, weil eine Transponierung genau diesen Tausch der Indizes darstellt, der einmal auf jede Zelle angewendet wird.

Jeder Wert wird einmal kopiert, daher beträgt die Laufzeit O(m × n), und das Raster benötigt O(m × n) Speicherplatz, den die Ausgabe ohnehin braucht. Das zeilenweise Lesen greift in der gespeicherten Reihenfolge auf den Speicher zu, und jede Ergebniszeile wird einmal mit ihrer endgültigen Größe angelegt.

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

Das Ergebnis mit der Form der Eingabe erstellen. Beim Beispiel mit 2 × 3 läuft result[2][0] über das Ende hinaus: Das Ergebnis benötigt n Zeilen der Länge m.
matrix[i][j] und matrix[j][i] direkt vertauschen. Das funktioniert nur, wenn m = n, und nur für Zellen mit j > i; eine Schleife über alle Zellen vertauscht jedes Paar zweimal und gibt die Matrix unverändert zurück.
In Python erstellt [[0] * m] * n n Verweise auf dieselbe Liste, sodass das Schreiben in eine Zelle eine ganze Spalte verändert. Erstelle jede Zeile einzeln.
In C liest der Aufrufer *returnSize als Anzahl der Ergebniszeilen, n, und (*returnColumnSizes)[j] als Länge jeder Zeile, m.

Häufige Fragen3

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?

O(m × n): Jeder der m × n Werte wird einmal kopiert, und weniger ist nicht möglich, um das Ergebnis zu erzeugen. Die neue Matrix benötigt O(m × n) Speicherplatz, also so viel wie die Ausgabe selbst.

Kannst du eine Matrix direkt transponieren?

Bei einer quadratischen Matrix: Ja. Vertausche matrix[i][j] mit matrix[j][i] für jede Zelle oberhalb der Diagonalen, mit O(1) zusätzlichem Speicher. Eine nicht quadratische Matrix ändert ihre Form, daher brauchst du bei einer Liste von Zeilen eine neue Matrix.

def transpose(matrix):
    # Schreibe hier den Code

Test #1

Test #2

Argument

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

Erwartete Ausgabe

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