Spiral Matrix

MoyenMaths et simulation Tableaux et chaînes

+10

Vous disposez d’une matrice d’entiers comportant m lignes et n colonnes, fournie sous forme de liste de lignes. Renvoyez toutes ses valeurs dans l’ordre spiralé.

Commencez dans le coin supérieur gauche et avancez vers la droite le long de la rangée du haut, puis vers le bas le long de la colonne de droite, vers la gauche le long de la rangée du bas et vers le haut le long de la colonne de gauche. Continuez à tourner en spirale vers l’intérieur dans le sens horaire jusqu’à ce que chaque valeur ait été lue exactement une fois.

Fonction

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

matrixinteger-2d-array: la grille d’entiers, sous forme d’une liste de lignes de même longueur
Renvoieinteger-array: chaque valeur de la matrice dans l’ordre spiralé dans le sens horaire, en commençant par le coin supérieur gauche

Contraintes

1 ≤ m, n ≤ 80, où m = matrix.length et n = matrix[i].length
Chaque ligne a la même longueur n.
-100 ≤ matrix[i][j] ≤ 100

Exemples

Entrée: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
Sortie: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Explication: Les valeurs augmentent le long de la spirale. L’anneau extérieur se lit ainsi : 1, 2, 3 en haut, 4, 5, 6 en descendant à droite, 7, 8 en revenant le long du bas et 9, 10 en remontant à gauche. La couche intérieure est une seule colonne, qui se lit une fois de haut en bas : 11, 12.

Entrée: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
Sortie: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
Explication: L’anneau extérieur donne 7, 1, 5, 3, puis 6, -1 en descendant le long du côté droit, 4, 0, 8 en revenant le long du bas et 2 en remontant le côté gauche. Il reste la rangée unique 9, -4, lue une fois de gauche à droite.

+15 tests cachés à la soumission

Pour aller plus loin

Peux-tu plutôt renvoyer les valeurs dans le sens antihoraire, en commençant par le coin supérieur gauche et en descendant d’abord la colonne de gauche ?

Indices

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

0 sur 3 ouverts

Solution

Il n’y a pas de formule mathématique astucieuse ici ; le problème consiste à suivre les éléments, et c’est là que les solutions échouent. Chaque coin doit être lu une seule fois, et non deux, et la couche la plus intérieure peut être une seule ligne ou une seule colonne, auquel cas un tour complet repasserait sur les mêmes valeurs. Tu peux avancer comme un robot qui tourne à droite dès qu’il est bloqué et se souvient des cellules qu’il a lues. Ou tu peux éplucher la matrice anneau par anneau à l’aide de quatre limites qui se resserrent, ce qui ne nécessite aucune mémoire supplémentaire.

Avance et tourne à droite lorsqu’un obstacle te bloque

Intuition

Imagine un marcheur placé dans la cellule en haut à gauche, face à droite. Il lit la cellule sur laquelle il se trouve, puis tente d’avancer. Si ce déplacement le ferait sortir de la matrice ou arriver sur une cellule qu’il a déjà lue, il tourne à droite (droite, bas, gauche, haut, puis de nouveau droite) et avance dans cette direction à la place. Cette règle trace la spirale : les bords de la matrice interrompent le premier tour, et les cellules déjà lues font office de murs pour tous les tours suivants.

Garde la direction sous forme d’un indice d dans deux petits tableaux, dr = [0, 1, 0, -1] et dc = [1, 0, -1, 0], de sorte qu’un virage à droite corresponde à d = (d+1) % 4. Garde une grille booléenne seen de la taille de la matrice. Dans le premier exemple, le marcheur lit 1, 2, 3, atteint le bord droit et tourne vers le bas pour lire 4, 5, 6, tourne à gauche pour lire 7, 8, puis vers le haut pour lire 9, 10. Au-dessus de 10 se trouve le 1, déjà lu : il tourne donc à droite et arrive sur 11. À droite de 11 se trouve le 4, déjà lu, donc il tourne vers le bas et arrive sur 12.

Exécute la boucle exactement m × n fois, une fois par cellule, et tu n’auras jamais besoin de détecter la fin. Après la dernière lecture, le marcheur peut faire face à un mur, mais il ne fait plus aucun pas. Chaque cellule est lue une seule fois : la complexité temporelle est donc O(m × n). La grille seen nécessite une mémoire supplémentaire de O(m × n), que l’approche suivante permet d’éviter.

Algorithme

Commence à la ligne 0, colonne 0, en regardant vers la droite, avec une grille seen entièrement à false.
Répète m × n fois : ajoute la valeur actuelle et marque sa cellule comme visitée.
Calcule la cellule suivante dans la direction actuelle. Si elle est en dehors de la matrice ou déjà visitée, tourne à droite et calcule-la à nouveau.
Déplace-toi vers cette cellule.
Renvoie les valeurs dans l’ordre où tu les as ajoutées.

def spiralOrder(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    # Directions in clockwise order: right, down, left, up.
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    r = c = d = 0
    result = []
    for _ in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        # Blocked by the edge or by a cell already read: turn right.
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return result

Épluche les couches avec quatre limites

Intuition

La spirale est un ensemble d’anneaux imbriqués. Décrivez l’anneau courant à l’aide de quatre limites : les lignes de top à bottom, les colonnes de left à right. Un tour parcourt la ligne du haut de left à right, la colonne de droite de top+1 jusqu’à bottom, la ligne du bas de right-1 à left, puis la colonne de gauche de bottom-1 jusqu’à top+1. Chaque côté commence une case après la fin du côté précédent, de sorte que chaque coin est lu exactement une fois. Déplacez ensuite les quatre limites d’un pas vers l’intérieur et recommencez tant que top ≤ bottom et left ≤ right.

Le piège est un anneau qui n’a qu’une seule ligne ou une seule colonne d’épaisseur, où le retour repasse sur des cases déjà lues. Dans le deuxième exemple, après l’anneau extérieur, les limites sont top = bottom = 1, left = 1 et right = 2 : la ligne unique 9, -4. La ligne du haut lit les deux valeurs et la colonne de droite ne contient rien sous top. Mais la ligne du bas est cette même ligne, et la parcourir en sens inverse ajouterait 9 une deuxième fois. Ne parcourez donc la ligne du bas et la colonne de gauche que lorsque top < bottom et left < right. Le troisième exemple est le cas symétrique : dans la colonne unique 4, 1, 7, remonter la colonne de gauche ferait lire 1 une nouvelle fois.

Chaque valeur est lue une fois, donc le temps d’exécution est de O(m × n), ce qui est le minimum possible puisque la réponse contient toutes les valeurs. En dehors de la réponse, la mémoire utilisée est de quatre entiers.

Algorithme

Définissez top = 0, bottom = m-1, left = 0, right = n-1.
Tant que top ≤ bottom et left ≤ right, lisez la ligne du haut de left à right et la colonne de droite de top+1 à bottom.
Si top < bottom et left < right, lisez la ligne du bas de right-1 à left et la colonne de gauche de bottom-1 à top+1.
Ajoutez un à top et left, soustrayez un de bottom et right.
Renvoyez les valeurs dans l’ordre où vous les avez lues.

def spiralOrder(matrix):
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []
    while top <= bottom and left <= right:
        # Top row, left to right, then right column, top to bottom.
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        for r in range(top + 1, bottom + 1):
            result.append(matrix[r][right])
        # A layer one row or one column thick has no way back:
        # walking back would read the same cells again.
        if top < bottom and left < right:
            # Bottom row, right to left, then left column, bottom to top.
            for c in range(right - 1, left - 1, -1):
                result.append(matrix[bottom][c])
            for r in range(bottom - 1, top, -1):
                result.append(matrix[r][left])
        # Step in to the next layer.
        top += 1
        bottom -= 1
        left += 1
        right -= 1
    return result

Pièges et cas limites

Les boucles sont courtes, donc les bogues se nichent dans les coins et dans la dernière couche.

Lire deux fois la dernière couche lorsqu’elle ne comporte qu’une ligne ou une colonne. Sans la vérification top < bottom et left < right, le deuxième exemple se termine par 9, -4, 9 et le troisième lit 4, 1, 7, 1.
Lire deux fois un coin. Si chaque côté va de sa première cellule à sa dernière, chaque coin est lu par deux côtés. Commence chaque côté une cellule après la fin du côté précédent.
Utiliser la boucle tant que top < bottom au lieu de top ≤ bottom. Elle s’arrête avant le milieu d’un carré impair : dans une matrice 3 × 3, la valeur centrale n’est jamais lue.
Confondre les lignes et les colonnes dans une matrice qui n’est pas carrée. Utiliser matrix.length pour les deux limites fonctionne pour tous les tests sur des matrices carrées, mais échoue sur une matrice 3 × 4.
Oublier les entrées minces : une ligne, une colonne, une cellule. Chacune constitue une seule couche qui n’atteint jamais la dernière ligne ni la colonne de gauche.
En R, a:b compte à rebours lorsque a > b, donc une plage vide telle que 3:2 donne 3, 2 au lieu de rien ; protège-la ou utilise seq_len. En Lua et en R, les lignes et les colonnes commencent à 1.

Questions fréquentes4

Quelle est la complexité en temps et en espace de la matrice en spirale ?

Les deux approches lisent chaque valeur une seule fois, donc la complexité temporelle est O(m × n), et aucune solution ne peut faire mieux puisque la réponse contient toutes les valeurs. Le parcours par couches avec quatre limites utilise O(1) de mémoire supplémentaire, en plus de la réponse. Le parcours qui tourne lorsqu’il est bloqué utilise une grille de taille O(m × n) pour mémoriser les cellules déjà lues.

Comment éviter de lire une valeur deux fois lors d’un parcours en spirale ?

Deux endroits provoquent des répétitions. Aux coins, commence chaque côté une cellule après la fin du côté précédent, afin que chaque coin n’appartienne qu’à un seul côté. Dans la dernière couche, lis la rangée du bas et la colonne de gauche uniquement si la couche comporte plus d’une rangée et plus d’une colonne, car sinon le trajet de retour passe sur des cellules que tu as déjà lues.

Comment remplir une matrice en spirale plutôt que d’en lire une ?

Utilisez les mêmes quatre limites et les mêmes quatre côtés, mais écrivez au lieu de lire. Gardez un compteur qui commence à 1 et stockez sa valeur dans chaque cellule au fur et à mesure, en l’incrémentant à chaque fois. Pour une matrice n × n, le compteur se termine à n², et le premier exemple ci-dessus montre le résultat obtenu pour une grille 4 × 3.

Pourquoi tourner à droite lorsqu’on est bloqué produit-il une spirale ?

Au premier tour, le marcheur tourne aux quatre bords de la matrice. À chaque tour suivant, les cellules déjà lues servent de murs : le marcheur tourne donc une cellule avant l’anneau parcouru au tour précédent. Ainsi, chaque tour reste à l’intérieur du précédent, ce qui forme la spirale. Le marcheur n’a pas besoin de savoir dans quelle couche il se trouve, mais seulement si la cellule suivante est libre.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

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