Transpose Matrix

Q: Qual è la complessità temporale della trasposizione di una matrice?

O(m × n) : ciascuno dei m × n valori viene copiato una volta, e non è possibile fare meno per ottenere la risposta. La nuova matrice occupa uno spazio O(m × n) , pari alla dimensione dell'output stesso.

Q: Puoi trasporre una matrice sul posto?

Per una matrice quadrata, sì: scambia matrix[i][j] con matrix[j][i] per ogni cella sopra la diagonale, usando O(1) di memoria aggiuntiva. Una matrice non quadrata cambia forma, quindi con un elenco di righe ti serve una nuova matrice.

PrincipianteArray e stringhe

+10

Ricevi una matrice di numeri interi sotto forma di elenco di righe: matrix[i][j] è il valore nella riga i, colonna j. Restituisci la sua trasposta: il valore nella riga i, colonna j si sposta nella riga j, colonna i, così ogni riga diventa una colonna. La matrice non deve essere quadrata: una matrice m × n diventa una matrice n × m.

Funzione

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

matrixinteger-2d-array: la matrice m × n, come elenco di m righe di n numeri interi
Restituisceinteger-2d-array: la trasposta n × m, come lista di n righe di m interi

Vincoli

1 ≤ m, n ≤ 1000, dove m = matrix.length e n = matrix[i].length
m × n ≤ 5000
Ogni riga ha la stessa lunghezza n.
-1000 ≤ matrix[i][j] ≤ 1000

Esempi

Input: matrix = [[1, 2, 3], [4, 5, 6]]
Output: [[1, 4], [2, 5], [3, 6]]
Spiegazione: La riga [1, 2, 3] diventa la prima colonna e [4, 5, 6] la seconda. Letto riga per riga, il risultato è [1, 4], [2, 5], [3, 6]: una matrice 3 × 2.

Per approfondire

Supponiamo che la matrice sia memorizzata come un unico array piatto di m × n valori, riga dopo riga. Riesci a trasporre una matrice non quadrata all’interno di quell’array, senza usare un secondo array?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

La trasposizione non calcola nulla: il valore in (i, j) si sposta in (j, i). Il lavoro consiste nella forma. La risposta ha n righe di lunghezza m, quindi una lista di righe non quadrata non può essere trasposta sul posto; crea una nuova matrice di dimensioni scambiate e riempila.

Leggi la matrice una colonna alla volta

Intuizione

La riga j della risposta è la colonna j dell’input, letta dall’alto verso il basso. Per [[1, 2, 3], [4, 5, 6]], la colonna 0 legge prima 1 e poi 4, quindi la prima riga della risposta è [1, 4].

Ogni valore viene letto una volta e scritto una volta: tempo O(m × n) e spazio O(m × n) per il risultato. La costruzione di ogni nuova riga salta da una riga dell’input all’altra, invece di leggere lungo una sola riga: è il modo più lento di scorrere la memoria.

Algoritmo

Sia m il numero di righe e n la lunghezza di una riga.
Per ogni colonna j da 0 a n-1, inizia una lista vuota.
Aggiungi matrix[i][j] a essa per ogni i da 0 a m-1.
Aggiungi la lista al risultato come riga j e restituisci il risultato dopo l'ultima colonna.

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

Riempi una nuova griglia n × m specchiando ogni cella

Intuizione

Crea in anticipo il risultato n × m, poi leggi l’input nell’ordine in cui è memorizzato, riga per riga, e inserisci ogni valore all’indirizzo speculare: result[j][i] = matrix[i][j]. È corretto perché una trasposizione consiste esattamente in questo scambio degli indici, applicato una volta a ogni cella.

Ogni valore viene copiato una volta, quindi il tempo è O(m × n) e la griglia occupa lo spazio O(m × n) che l’output richiede comunque. Leggere per righe visita la memoria nell’ordine in cui è memorizzata, e ogni riga del risultato viene allocata una sola volta, con la sua dimensione finale.

Algoritmo

Sia m il numero di righe e n la lunghezza di una riga.
Crea result con n righe, ciascuna contenente m valori.
Per ogni riga i e ogni colonna j dell'input, imposta result[j][i] = matrix[i][j].
Restituisci result.

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

Trappole e casi limite

Costruire il risultato con la stessa forma dell'input. Nell'esempio 2 × 3, scrivere result[2][0] supera il limite: il risultato deve avere n righe di lunghezza m.
Scambiare matrix[i][j] con matrix[j][i] sul posto. Funziona solo quando m = n e solo per le celle con j > i; un ciclo su ogni cella scambia ogni coppia due volte e restituisce la matrice invariata.
In Python, [[0] * m] * n crea n riferimenti a un'unica lista, quindi scrivere in una cella scrive in un'intera colonna. Crea ogni riga separatamente.
In C, il chiamante legge *returnSize come il numero di righe del risultato, n, e (*returnColumnSizes)[j] come la lunghezza di ogni riga, m.

Domande frequenti3

Che cos'è la trasposta di una matrice?

È la matrice che ottieni scambiando righe e colonne: il valore nella riga i, colonna j si sposta nella riga j, colonna i. Una matrice 2 × 3 diventa 3 × 2 e, trasponendola due volte, si ottiene di nuovo la matrice originale.

Qual è la complessità temporale della trasposizione di una matrice?

O(m × n): ciascuno dei m × n valori viene copiato una volta, e non è possibile fare meno per ottenere la risposta. La nuova matrice occupa uno spazio O(m × n), pari alla dimensione dell'output stesso.

Puoi trasporre una matrice sul posto?

Per una matrice quadrata, sì: scambia matrix[i][j] con matrix[j][i] per ogni cella sopra la diagonale, usando O(1) di memoria aggiuntiva. Una matrice non quadrata cambia forma, quindi con un elenco di righe ti serve una nuova matrice.

def transpose(matrix):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

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

Output atteso

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