Rotate Image

Q: Qual è la complessità temporale e spaziale della rotazione di una matrice?

Ruotare una matrice n × n richiede un tempo O(n²), poiché quasi ogni valore deve essere spostato una volta. Il metodo trasponi e inverti richiede O(1) spazio aggiuntivo. Creare una copia ruotata richiede anch’esso un tempo O(n²), ma usa O(n²) spazio aggiuntivo.

MedioArray e stringhe Matematica e simulazione

+10

Ti viene fornita una griglia n × n di numeri interi, una lista per riga. Ruotala di un quarto di giro in senso orario e restituiscila. La riga superiore diventa la colonna più a destra, la seconda riga la colonna alla sua sinistra e così via: il valore in (i, j) finisce in (j, n-1-i). Puoi modificare la griglia sul posto; restituiscila.

Funzione

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

matrixinteger-2d-array: la griglia quadrata, una lista interna per ogni riga
Restituisceinteger-2d-array: la matrice è stata ruotata di 90 gradi in senso orario

Vincoli

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

Esempi

Input: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
Output: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
Spiegazione: La prima riga, 3 7 1, diventa l'ultima colonna, letta dall'alto verso il basso. La prima colonna, 3 9 4, letta dal basso verso l'alto, diventa la prima riga [4, 9, 3]. Il valore centrale 5 resta al suo posto.

Per approfondire

Quali due passaggi in-place ruotano la matrice di 180 gradi, e puoi farlo con un unico passaggio di scambi?

Suggerimenti

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

0 di 3 aperti

Soluzione

La posizione in cui va ciascun valore è determinata da una formula: (i, j) si sposta in (j, n-1-i). La parte difficile è spostare i valori senza una seconda matrice, perché scrivere un valore nella sua nuova cella sovrascrive un valore che non è ancora stato spostato. Una trasposizione seguita dall’inversione di una riga produce la stessa rotazione di un quarto di giro tramite scambi a coppie.

Costruisci una copia ruotata

Intuizione

La riga i diventa la colonna n-1-i e il valore in posizione j nella riga finisce in posizione j lungo quella colonna, che corrisponde alla riga j. Quindi result[j][n-1-i] = matrix[i][j]. Nel primo esempio, il 4 alla riga 2, colonna 0, va alla riga 0, colonna 0, ed è per questo che la risposta inizia con 4.

I valori si spostano lungo cicli di quattro, quindi scrivere direttamente nella matrice originale cancellerebbe un valore prima che possa spostarsi: il 3 sovrascriverebbe l'1 nell'angolo in alto a destra. La copia richiede n² celle aggiuntive, 4.900 per n = 70.

Algoritmo

Crea una matrice risultato n × n.
Per ogni riga i e colonna j, copia matrix[i][j] in result[j][n-1-i].
Restituisci il risultato.

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

Trasponi, poi inverti ogni riga

Intuizione

Una trasposizione sposta (i, j) in (j, i), mentre invertire una riga sposta la colonna c nella colonna n-1-c. Insieme spostano (i, j) in (j, n-1-i), esattamente nella posizione in cui la rotazione lo colloca.

Entrambe le operazioni vengono eseguite sul posto perché ciascuna consiste in una serie di scambi a coppie. In una trasposizione, matrix[i][j] e matrix[j][i] devono trovarsi ciascuna nella cella dell'altra, quindi basta un solo scambio per sistemarle entrambe. Scambia solo le coppie con j > i, altrimenti ogni coppia viene scambiata di nuovo nella posizione iniziale. Invertire una riga significa scambiare le sue due estremità e procedere verso il centro.

Nel primo esempio, la trasposizione produce [[3, 9, 4], [7, 5, 8], [1, 2, 6]]: ogni riga ora contiene una colonna dell'originale. Invertendo ogni riga si ottiene la risposta.

La trasposizione effettua n(n-1)/2 scambi e le inversioni n·⌊n/2⌋, quindi il lavoro è O(n²) e richiede poche variabili di memoria aggiuntiva. La versione R prima copia l'input in una matrice R, quindi la memoria aggiuntiva è O(n²).

Algoritmo

Per ogni cella sopra la diagonale principale, (i, j) con j > i, scambia il suo valore con quello della cella (j, i).
Per ogni riga, scambia il primo e l'ultimo valore e procedi verso l'interno da entrambe le estremità finché non si incontrano.
Restituisci la matrice.

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

Trappole e casi limite

Trasporre con j che parte da 0. Ogni coppia viene scambiata due volte, annullando la trasposizione, quindi il risultato è solo l’inversione dell’ordine delle righe, come in un’immagine speculare.
Invertire prima di trasporre. Questo ordine ruota la matrice in senso antiorario. Un test con una matrice 2 × 2 lo rileva: [[1, 2], [3, 4]] deve diventare [[3, 1], [4, 2]].
Scrivere matrix[j][n-1-i] = matrix[i][j] nella stessa matrice. La cella di destinazione contiene ancora un valore che non è stato spostato, e questo valore va perso.
Usare n-i invece di n-1-i. Con gli indici a base 0, l’ultima colonna è n-1, quindi n-i supera il limite per i = 0.

Domande frequenti3

Qual è la complessità temporale e spaziale della rotazione di una matrice?

Ruotare una matrice n × n richiede un tempo O(n²), poiché quasi ogni valore deve essere spostato una volta. Il metodo trasponi e inverti richiede O(1) spazio aggiuntivo. Creare una copia ruotata richiede anch’esso un tempo O(n²), ma usa O(n²) spazio aggiuntivo.

Come si ruota una matrice in senso antiorario?

Inverti l’ordine dei due passaggi: prima inverti ogni riga, poi trasponi. Puoi anche trasporre e poi invertire l’ordine delle righe. In entrambi i casi, il valore in (i, j) finisce in (n-1-j, i).

Riesci a ruotare una matrice spostando quattro valori alla volta?

Sì. Ogni valore al di fuori del centro appartiene a un ciclo di quattro celle: (i, j), (j, n-1-i), (n-1-i, n-1-j) e (n-1-j, i). Anello per anello, conserva in una variabile un valore di ogni ciclo e sposta gli altri tre. Ha lo stesso tempo O(n²) e lo stesso spazio O(1), ma con più calcoli sugli indici in cui è facile sbagliare.

def rotateImage(matrix):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

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

Output atteso

[[4, 9, 3], [8, 5, 7], [6, 2, 1]]