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 }
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 -
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; }
Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3
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!