Exercice d'algorithme 5

Rotate Array

La description

Lorsque deux arguments, un tableau de type entier et un entier N (nombre de rotations), sont passés, les éléments du tableau sont déplacés N fois (moins vers la gauche, plus vers la droite). Faisons un tableau pivoté.

Exemple

Supposons que la séquence suivante soit passée. Si la vitesse de rotation N est -1, tous les éléments sont décalés un par un vers la gauche. Aussi, si le nombre de tours N est égal à 2, tous les éléments sont décalés un par un deux fois vers la droite.

Try It Yourself (Brute Force) La première chose qui m'est venue à l'esprit sur ce problème était l'algorithme de force brute après rotation Il y aura toujours deux tableaux partiels à gauche et à droite, alors créez ces deux tableaux. (Dans le cas de N = 2 dans l'exemple, left_sub_array = {9, 40} et right_sub_array = {1, 10, 20, 0, 59, 86, 32, 11}) Ensuite, les éléments pivotés stockés dans les sous-tableaux gauche et droit sont mis à jour séquentiellement dans le tableau d'origine. Si N est négatif, autorisez l'application de la rotation gauche à l'algorithme de rotation droite.

Complexité d'exécution O (n)

Calcul spatial (complexité de la mémoire) O (n)

la mise en oeuvre

TEST

OUTPUT

La revue

Afin de changer l'ordre des éléments, il est nécessaire de réorganiser les positions de tous les éléments, donc le temps d'exécution O (n) est la limite. Cependant, la quantité de calcul spatial peut être O (1). Autrement dit, il utilise uniquement la structure de données transmise.

Optimisation: Complexité de la mémoire O (n) -> O (1)

1. Inversez les éléments du tableau d'origine.
2. Inversez les éléments de 0 à N-1.
3. Inverser les éléments de N à Longueur-1

Exemple

Supposons que la même séquence que dans l'exemple précédent soit passée. Le nombre de rotations est N = 2.

1. Commencez par inverser tous les éléments du tableau d'origine.
2. Puis inversez les éléments de l'indice 0 à N-1 (2-1 = 1).
3. Enfin, inversez les éléments de N (2) à la fin du tableau. Maintenant, la quantité de calcul spatial peut être optimisée avec la constante O (1).

la mise en oeuvre

SORTIE (même code TEST)