Transpose Matrix

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

È O(m × n) , perché ciascuno dei m × n valori viene copiato una volta e niente di meno può produrre la risposta. La nuova matrice richiede uno spazio O(m × n) , che corrisponde alla dimensione dell'output stesso.

Q: È possibile 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 memoria aggiuntiva O(1) . Per una matrice non quadrata il risultato ha una forma diversa, quindi con un elenco di righe serve una nuova matrice.

Q: Come si traspone una matrice non quadrata?

Crea un risultato con n righe di lunghezza m , mentre l’input ha m righe di lunghezza n . Poi copia ogni valore con result[j][i] = matrix[i][j] . L’idea della diagonale del caso quadrato non si applica, perché le due matrici non hanno la stessa forma.

PrincipianteArray e stringhe

+10

Ricevi una matrice di numeri interi come elenco di righe: matrix[i][j] è il valore nella riga i, colonna j. Restituisci la sua trasposta, la matrice che ottieni trasformando ogni riga in una colonna. Il valore nella riga i, colonna j si sposta nella riga j, colonna i. 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 elenco 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 prima riga [1, 2, 3] diventa la prima colonna e [4, 5, 6] la seconda. Leggendo il risultato riga per riga si ottiene [1, 4], [2, 5], [3, 6]: la matrice 2 × 3 è diventata una matrice 3 × 2.

+15 test nascosti all’invio

Per approfondire

Supponiamo che la matrice sia memorizzata come un unico array lineare di m × n valori, una riga dopo l’altra. 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 è un semplice cambio di posizione: il valore in (i, j) si sposta in (j, i) e non viene calcolato nulla. Il lavoro consiste nel dare alla matrice la forma giusta. Una matrice non quadrata memorizzata come lista di righe non può essere trasposta sul posto, perché il risultato ha n righe di lunghezza m invece di m righe di lunghezza n, quindi si crea una nuova matrice delle dimensioni scambiate e la si riempie.

Leggi la matrice una colonna alla volta

Intuizione

La riga j della risposta è la colonna j dell'input, letta dall'alto verso il basso. Quindi costruisci la risposta una riga alla volta: per ogni colonna j da 0 a n-1, raccogli matrix[0][j], matrix[1][j] e così via fino a matrix[m-1][j], quindi aggiungi quell'elenco come riga successiva.

Per [[1, 2, 3], [4, 5, 6]], la colonna 0 legge 1 e poi 4, la colonna 1 legge 2 e poi 5, la colonna 2 legge 3 e poi 6. La risposta è [[1, 4], [2, 5], [3, 6]], con n = 3 righe di m = 2 valori.

Ogni valore viene letto una volta e scritto una volta, quindi il tempo è O(m × n) e il risultato occupa O(m × n) spazio. Il costo è nel modello di accesso: costruire una nuova riga tocca ogni riga dell'input, passando da una riga all'altra invece di leggere lungo una sola.

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] alla lista 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 rispecchiando ogni cella

Intuizione

Decidi prima la forma, poi riempila. La risposta ha n righe di lunghezza m, quindi crea subito quella griglia. Poi leggi l’input nel suo ordine naturale, riga per riga e da sinistra a destra, e inserisci ogni valore all’indirizzo speculare: result[j][i] = matrix[i][j].

La regola è corretta perché trasporre consiste esattamente nello scambiare i due indici. Nell’esempio quadrato [[1, 2], [3, 4]], l’1 e il 4 sulla diagonale restano dove sono, il 2 passa da (0, 1) a (1, 0) e il 3 da (1, 0) a (0, 1), ottenendo [[1, 3], [2, 4]].

Ciascuno dei m × n valori viene copiato una volta, quindi il tempo è O(m × n), mentre la nuova griglia occupa lo spazio O(m × n) richiesto comunque dall’output. Leggendo l’input lungo le righe si visita la memoria nell’ordine in cui è memorizzata, e ogni riga del risultato viene creata 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, ognuna 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

Quasi tutte le risposte sbagliate dipendono dalla forma, non dai valori.

Costruire il risultato con la forma originale. Un risultato di m righe e n colonne funziona solo con un input quadrato; nell’esempio 2 × 3, scrivere result[2][0] supera i limiti. Il risultato deve avere n righe di lunghezza m.
Scambiare gli elementi in-place in una matrice non quadrata. Scambiare matrix[i][j] con matrix[j][i] funziona solo quando m = n e, anche in quel caso, il ciclo deve includere solo le celle sopra la diagonale (j > i), altrimenti ogni coppia viene scambiata due volte e la matrice torna invariata.
Condividere lo stesso oggetto riga. In Python, [[0] * m] * n crea n riferimenti alla stessa lista, quindi scrivere in una cella modifica l’intera colonna. Crea ogni riga separatamente.
Dimenticare le dimensioni delle colonne in C. Il chiamante legge *returnSize come numero di righe del risultato, n, e (*returnColumnSizes)[j] come lunghezza di ogni riga, m.

Domande frequenti4

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), perché ciascuno dei m × n valori viene copiato una volta e niente di meno può produrre la risposta. La nuova matrice richiede uno spazio O(m × n), che corrisponde alla dimensione dell'output stesso.

È possibile 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 memoria aggiuntiva O(1). Per una matrice non quadrata il risultato ha una forma diversa, quindi con un elenco di righe serve una nuova matrice.

Come si traspone una matrice non quadrata?

Crea un risultato con n righe di lunghezza m, mentre l’input ha m righe di lunghezza n. Poi copia ogni valore con result[j][i] = matrix[i][j]. L’idea della diagonale del caso quadrato non si applica, perché le due matrici non hanno la stessa forma.

Python

def transpose(matrix):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

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

Atteso

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