[JAVA] 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. Screen Shot 2019-12-18 at 10.24.31.png Si la vitesse de rotation N est -1, tous les éléments sont décalés un par un vers la gauche. Screen Shot 2019-12-18 at 10.25.05.png 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. Screen Shot 2019-12-18 at 10.27.40.png

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

Screen Shot 2019-12-18 at 10.54.04.png

TEST Screen Shot 2019-12-18 at 11.29.13.png

OUTPUT Screen Shot 2019-12-18 at 11.30.31.png

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. Screen Shot 2019-12-18 at 11.16.56.png

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

la mise en oeuvre

Screen Shot 2019-12-18 at 11.34.01.png

SORTIE (même code TEST)

Screen Shot 2019-12-18 at 11.35.56.png

Recommended Posts

Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Exercice d'algorithme 6
Gymnastique algorithmique 24 Inverser une liste liée
Algorithme Python
Exercices d'algorithme 13
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes