Algorithme d'inversion 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 }

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;
}

Sortie

Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3

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!