Problème

Soit une matrice carrée matrix de dimensions n × n représentant une image. Vous devez la faire pivoter de 90 degrés dans le sens horaire, sur place (c'est-à-dire sans utiliser une autre matrice).

Approches

L'idée fondamentale est que l'élément situé à la ligne i et colonne j se retrouve après rotation à la position j de l'avant-dernière colonne, soit : result[j][n-1-i] = original[i][j]. Il faut ensuite appliquer cette transformation sur place.

Méthode 1 : Matrice auxiliaire (non cofnorme)

Cette méthode utilise un espace supplémentaire, mais l'affectation finale matrix[:] = aux modifie bien le contenu de l'entrée.

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        aux = [[0] * n for _ in range(n)]
        for ligne in range(n):
            for col in range(n):
                aux[col][n - 1 - ligne] = matrix[ligne][col]
        matrix[:] = aux

Méthode 2 : Rotation sur place par groupes de quatre

On échange cycliquement quatre éléments à la fois. On ne parcourt qu'un quart de la matrice.

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # Parcourir les coins supérieurs gauche des carrés concentriques
        for i in range(n // 2):
            for j in range((n + 1) // 2):
                # Stockage temporaire
                tmp = matrix[i][j]
                # 4 échanges en cercle
                matrix[i][j] = matrix[n - 1 - j][i]
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
                matrix[j][n - 1 - i] = tmp

Méthode 3 : Deux réflexions successives

On effectue d'abord un retournement horizontal (miroir sur l'axe vertical central), puis une transposition par rapport à la diagonale principale.

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # Retournement horizontal
        for ligne in range(n // 2):
            for col in range(n):
                matrix[ligne][col], matrix[n - 1 - ligne][col] = \
                    matrix[n - 1 - ligne][col], matrix[ligne][col]
        # Transposition (diagonale principale)
        for ligne in range(n):
            for col in range(ligne):
                matrix[ligne][col], matrix[col][ligne] = \
                    matrix[col][ligne], matrix[ligne][col]