Rotate Array

Q: Que se passe-t-il lorsque k est supérieur à la longueur du tableau ?

Tous les n pas ramènent le tableau à son ordre initial ; seuls les k mod n pas comptent donc. Faire pivoter [10, 20, 30] de 7 positions revient à le faire pivoter de 1 position, ce qui donne [30, 10, 20] . Lorsque k est un multiple de n , le tableau ne change pas.

Q: Comment faire pivoter un tableau vers la gauche ?

Une rotation vers la gauche de k équivaut à une rotation vers la droite de n - (k mod n) . Avec des inversions, inversez les premières k mod n valeurs, puis le reste, puis le tableau entier. Dans les deux cas, le temps d’exécution reste en O(n).

MoyenTableaux et chaînes Deux pointeurs

+10

Vous recevez un tableau d’entiers nums et un nombre k. Faites pivoter le tableau vers la droite de k positions : à chaque étape, chaque valeur se déplace d’une place vers la droite, et la dernière valeur revient au début. Renvoyez le tableau pivoté.

k peut être bien supérieur à la longueur du tableau.

Fonction

rotate(nums: integer-array, k: integer) → integer-array

numsinteger-array: le tableau d’entiers à faire pivoter
kinteger: combien d’étapes pour tourner à droite
Renvoieinteger-array: nums décalé vers la droite de k positions

Contraintes

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
0 ≤ k ≤ 10⁹

Exemples

Entrée: nums = [4, 9, 1, 6, 3]k = 2
Sortie: [6, 3, 4, 9, 1]
Explication: Deux pas vers la droite amènent les deux dernières valeurs, 6 et 3, au début. Les trois autres valeurs se déplacent de deux places vers la droite et conservent leur ordre : [6, 3, 4, 9, 1].

Pour aller plus loin

Peux-tu effectuer une rotation sur place en déplaçant chaque valeur directement à (i + k) mod n et en poursuivant avec la valeur qu’elle déloge ? Combien de cycles cela forme-t-il ?

Indices

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

0 sur 3 ouverts

Solution

Tous les n pas ramènent le tableau à son point de départ, donc réduisez d’abord k, qui peut valoir 10^9, à k mod n. Ensuite, écrivez chaque valeur directement à son indice final dans un deuxième tableau, ou obtenez le même résultat dans le tableau avec trois inversions et O(1) mémoire supplémentaire.

Copiez chaque valeur à son nouvel index

Intuition

Après k étapes, la valeur à l’indice i se trouve à l’indice (i + k) mod n ; écrivez-la donc directement à cet endroit sans effectuer les étapes. Réduisez d’abord k à k mod n : une rotation de n remet chaque valeur à sa place initiale, donc avec k = 7 et n = 3, il ne reste qu’une étape.

Un seul parcours place les n valeurs : temps O(n), plus mémoire O(n) pour le résultat. Vous ne pouvez pas écrire directement dans nums de cette façon, car chaque écriture écraserait une valeur que vous n’avez pas encore déplacée.

Algorithme

Définissez n comme étant la longueur de nums et remplacez k par k modulo n.
Créez un tableau de résultats de longueur n.
Pour chaque indice i, stockez nums[i] à l’emplacement result[(i + k) mod n].
Renvoyez le résultat.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = nums[i]
    return result

Trois inversions sur place

Intuition

Divise le tableau en A, les n-k premières valeurs, et B, les k dernières. Le tableau pivoté est constitué de B suivi de A, chaque bloc conservant son ordre initial. Inverser le tableau entier inverse à la fois l’ordre des blocs et l’ordre des éléments dans chacun d’eux : B vient donc en premier, mais se lit à l’envers, tout comme A. Inverser à nouveau chaque bloc rétablit son ordre intérieur.

Pour [4, 9, 1, 6, 3] et k = 2 : inverser tout le tableau donne [3, 6, 1, 9, 4], inverser les deux premiers éléments donne [6, 3, 1, 9, 4], et inverser les trois derniers donne [6, 3, 4, 9, 1].

Chaque valeur est échangée au plus deux fois ; la complexité temporelle est donc O(n), et la mémoire supplémentaire se limite à quelques variables d’indice (O(n) en R, qui copie le vecteur lorsque la fonction auxiliaire d’inversion le modifie).

Algorithme

Définis n comme la longueur de nums et remplace k par k mod n.
Inverse le tableau entier, des indices 0 à n-1.
Inverse le premier bloc, des indices 0 à k-1.
Inverse le deuxième bloc, des indices k à n-1.
Renvoie nums.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing

    def reverse(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    reverse(0, n - 1)  # the last k values come to the front, backwards
    reverse(0, k - 1)  # put the front block back in order
    reverse(k, n - 1)  # and the back block
    return nums

Pièges et cas limites

Oublier k mod n. Avec k = 10^9, la rotation pas à pas ne se termine jamais, et inverser les k premières valeurs lit bien au-delà de la fin du tableau.
Découper sans appliquer le modulo. En Python, nums[-k:] + nums[:-k] avec k = 7 et n = 3 renvoie le tableau inchangé, car les deux tranches s’arrêtent au bord du tableau.
Inverser dans le mauvais ordre. Inverser d’abord les deux blocs, puis le tableau entier revient à effectuer une rotation à gauche.
Erreur de décalage d’une unité à la frontière des blocs : le premier bloc se termine à l’index k-1 et le second commence à k. En Lua et en R, qui commencent à compter à 1, les blocs sont 1..k et k+1..n.

Questions fréquentes3

Quelle est la complexité temporelle de Rotate Array ?

O(n) à la fois pour l’approche par copie et pour les trois inversions, car chaque valeur est déplacée un nombre constant de fois. Réduire d’abord k avec k mod n évite qu’un k énorme ait de l’importance. Faire pivoter d’un pas à la fois coûte plutôt O(n × k).

Que se passe-t-il lorsque k est supérieur à la longueur du tableau ?

Tous les n pas ramènent le tableau à son ordre initial ; seuls les k mod n pas comptent donc. Faire pivoter [10, 20, 30] de 7 positions revient à le faire pivoter de 1 position, ce qui donne [30, 10, 20]. Lorsque k est un multiple de n, le tableau ne change pas.

Comment faire pivoter un tableau vers la gauche ?

Une rotation vers la gauche de k équivaut à une rotation vers la droite de n - (k mod n). Avec des inversions, inversez les premières k mod n valeurs, puis le reste, puis le tableau entier. Dans les deux cas, le temps d’exécution reste en O(n).

def rotate(nums, k):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

nums = [4, 9, 1, 6, 3]
k = 2

Résultat attendu

[6, 3, 4, 9, 1]