#algorithme #code

Il est possible de faire une rotation d’array de k places en O(n), sans utiliser de mémoire supplémentaire.

Exemple d’une rotation de 2 vers la droite donne: - avant : 1 2 3 4 5 6 - après : 5 6 1 2 3 4

Pour cela: 1. inverser les n-k premiers éléments 2. inverser le reste 3. inverser le tout

Dans l’exemple (n=6 et k=2) - après 1) 4 3 2 1 5 6 - après 2) 4 3 2 1 6 5 - après 3) 5 6 1 2 3 4