Rotate Image

Q: Quelle est la complexité temporelle et spatiale de la rotation d’une matrice ?

Faire pivoter une matrice n × n prend un temps O(n²), puisque presque chaque valeur doit être déplacée une fois. La méthode de transposition puis d’inversion nécessite un espace supplémentaire O(1). La création d’une copie pivotée prend également un temps O(n²), mais utilise un espace supplémentaire O(n²).

MoyenTableaux et chaînes Maths et simulation

+10

On vous donne une grille n × n d’entiers, une liste par ligne. Faites-la pivoter d’un quart de tour dans le sens horaire et renvoyez-la. La première ligne devient la colonne la plus à droite, la deuxième ligne la colonne située à sa gauche, et ainsi de suite : la valeur en (i, j) se retrouve en (j, n-1-i). Vous pouvez modifier la grille sur place ; renvoyez-la.

Fonction

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

matrixinteger-2d-array: la grille carrée, une liste interne par ligne
Renvoieinteger-2d-array: la matrice a pivoté de 90 degrés dans le sens des aiguilles d’une montre

Contraintes

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

Exemples

Entrée: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
Sortie: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
Explication: La première ligne, 3 7 1, devient la dernière colonne, lue de haut en bas. La première colonne, 3 9 4, lue de bas en haut, devient la première ligne [4, 9, 3]. La valeur centrale 5 reste en place.

Pour aller plus loin

Quelles sont les deux opérations en place qui font pivoter la matrice de 180 degrés, et peux-tu le faire en un seul passage d’échanges ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La destination de chaque valeur est donnée par une formule : (i, j) devient (j, n-1-i). La difficulté consiste à déplacer les valeurs sans utiliser une deuxième matrice, car écrire une valeur dans sa nouvelle cellule écrase une valeur qui n’a pas encore été déplacée. Une transposition suivie d’une inversion des lignes produit le même quart de tour au moyen d’échanges par paires.

Créer une copie pivotée

Intuition

La ligne i devient la colonne n-1-i, et la valeur à la position j dans la ligne arrive à la position j le long de cette colonne, qui est la ligne j. Donc result[j][n-1-i] = matrix[i][j]. Dans le premier exemple, le 4 à la ligne 2, colonne 0 va à la ligne 0, colonne 0, ce qui explique pourquoi la réponse commence par 4.

Les valeurs se déplacent selon des cycles de quatre, donc écrire en place effacerait une valeur avant qu’elle ne se déplace : le 3 écraserait le 1 dans le coin supérieur droit. La copie coûte n² cellules supplémentaires, 4,900 pour n = 70.

Algorithme

Créez une matrice résultat n × n.
Pour chaque ligne i et chaque colonne j, copiez matrix[i][j] dans result[j][n-1-i].
Renvoyez le résultat.

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

Transposer, puis inverser chaque ligne

Intuition

Une transposition déplace (i, j) vers (j, i), et l’inversion d’une ligne déplace la colonne c vers la colonne n-1-c. Ensemble, ces opérations déplacent (i, j) vers (j, n-1-i), exactement à l’endroit où la rotation le place.

Les deux opérations s’effectuent en place, car chacune consiste en une série d’échanges par paires. Dans une transposition, matrix[i][j] et matrix[j][i] doivent chacune occuper la cellule de l’autre : un seul échange suffit donc pour les deux. Échange uniquement les paires pour lesquelles j > i, sinon chaque paire sera échangée deux fois et reviendra à sa position initiale. L’inversion d’une ligne échange ses deux extrémités, puis progresse vers le centre.

Dans le premier exemple, la transposition donne [[3, 9, 4], [7, 5, 8], [1, 2, 6]] : chaque ligne contient désormais une ancienne colonne. L’inversion de chaque ligne donne la réponse.

La transposition effectue n(n-1)/2 échanges, et les inversions n·⌊n/2⌋ ; le travail est donc de O(n²), avec quelques variables supplémentaires en mémoire. La version R copie d’abord l’entrée dans une matrice R : sa mémoire supplémentaire est donc de O(n²).

Algorithme

Pour chaque cellule située au-dessus de la diagonale principale, (i, j) avec j > i, échangez sa valeur avec celle de la cellule (j, i).
Pour chaque ligne, échangez sa première et sa dernière valeur, puis rapprochez les deux extrémités vers l’intérieur jusqu’à ce qu’elles se rejoignent.
Retournez 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

Pièges et cas limites

Transposer en commençant par j à 0. Chaque paire est échangée deux fois, ce qui annule la transposition ; le résultat est donc uniquement les lignes inversées, comme dans un miroir.
Inverser avant de transposer. Cet ordre fait tourner la matrice dans le sens antihoraire. Un test avec une matrice 2 × 2 permet de le détecter : [[1, 2], [3, 4]] doit devenir [[3, 1], [4, 2]].
Écrire matrix[j][n-1-i] = matrix[i][j] dans la même matrice. La cellule cible contient encore une valeur qui n’a pas été déplacée, et celle-ci est perdue.
Utiliser n-i au lieu de n-1-i. Avec des indices commençant à 0, la dernière colonne est n-1, donc n-i dépasse la limite pour i = 0.

Questions fréquentes3

Quelle est la complexité temporelle et spatiale de la rotation d’une matrice ?

Faire pivoter une matrice n × n prend un temps O(n²), puisque presque chaque valeur doit être déplacée une fois. La méthode de transposition puis d’inversion nécessite un espace supplémentaire O(1). La création d’une copie pivotée prend également un temps O(n²), mais utilise un espace supplémentaire O(n²).

Comment faire pivoter une matrice dans le sens antihoraire ?

Inversez l’ordre des deux étapes : inversez d’abord chaque ligne, puis transposez. Vous pouvez aussi transposer puis inverser l’ordre des lignes. Dans les deux cas, la valeur en (i, j) se retrouve en (n-1-j, i).

Peux-tu faire pivoter une matrice en déplaçant quatre valeurs à la fois ?

Oui. Chaque valeur à l’extérieur du centre appartient à un cycle de quatre cellules : (i, j), (j, n-1-i), (n-1-i, n-1-j) et (n-1-j, i). Anneau par anneau, garde une valeur de chaque cycle dans une variable et décale les trois autres. La complexité reste de O(n²) en temps et de O(1) en espace, avec davantage de calculs d’indices susceptibles d’être incorrects.

def rotateImage(matrix):
    # Écrivez le code ici

Test #1

Test #2

Argument

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

Résultat attendu

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