Maison > développement back-end > C++ > Algorithme d'inversion pour la rotation à droite du tableau écrit en C++

Algorithme d'inversion pour la rotation à droite du tableau écrit en C++

WBOY
Libérer: 2023-09-08 20:17:02
avant
1043 Les gens l'ont consulté

Algorithme dinversion pour la rotation à droite du tableau écrit en C++

Dans cet article, nous découvrirons l'algorithme d'inversion pour faire pivoter un tableau donné vers la droite de k éléments comme −

Input : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4
Output : { 43, 7, 3, 7, 4, 6, 2, 6 }
Explanation : Rotating each element of array by 4-element to the right gives { 43, 7, 3, 7, 4, 6, 2, 6 }.

Input : arr[ ] = { 8, 5, 8, 2, 1, 4, 9, 3 }, k = 3
Output : { 4, 9, 3, 8, 5, 8, 2, 1 }
Copier après la connexion

Comment trouver la solution

en déplaçant chaque élément vers la droite et en répétant le processus k fois , vous pouvez facilement résoudre ce problème. Mais cela prendra plus de temps car sa complexité temporelle est O(k * N).

Algorithme d'inversion : l'inversion est l'inversion d'un tableau, la rotation d'un tableau peut être effectuée en inversant certaines plages d'éléments. Selon cet algorithme -

  • Tout d'abord, inversez tout le tableau.
  • Modifiez k modulo k modulo N (taille du tableau), puisque k est supérieur à N.
  • Inversez les k premiers éléments du tableau pour les mettre dans l'ordre.
  • Inversez ensuite la plage des éléments restants, c'est-à-dire de k à N-1.
  • li>

Exemple

using namespace std;
#include <bits/stdc++.h>

void reverse(int nums[], int start,int end) {
   int temp=0;
   // reversing array with swapping start element with end element.
   while(start<=end){
      temp=nums[end];
      nums[end]=nums[start];
      nums[start]=temp;
      start++;
      end--;
   }
}

int main() {
   int arr[] = {4, 6, 2, 6, 43, 7, 3, 6, 2, 4, 5 };

   int N = sizeof(arr)/sizeof(arr[0]);

   int k = 4;
   // reversing whole array
   reverse(arr, 0, N-1);
   k = k%N;
   // reversing element range of 0 to k-1.

   reverse(arr, 0, k-1);
   // reversing element range of k to last element.
   reverse(arr, k, N-1);
   cout << "Array after rotating by k-elements : ";
   for(int i = 0;i<N;i++)
      cout << arr[i] << " ";
   return 0;
}
Copier après la connexion

Sortie

Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3
Copier après la connexion

Conclusion

Dans cet article, nous avons discuté du problème de la rotation à droite d'un tableau par k éléments en utilisant l'algorithme d'inversion. Nous avons discuté de ce qu'est l'algorithme d'inversion et de la manière de le mettre en œuvre pour résoudre ce problème. Nous avons également discuté du code C++ pour résoudre ce problème. Nous pouvons écrire ce code dans n'importe quel autre langage comme C, Java, Python, etc. J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

source:tutorialspoint.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal