Heim >Backend-Entwicklung >C++ >Inversionsalgorithmus für die Rechtsdrehung eines Arrays, geschrieben in C++
In diesem Artikel lernen wir den Umkehralgorithmus kennen, um ein gegebenes Array um k Elemente nach rechts zu drehen, wie z. B. −
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 }
indem man jedes Element nach rechts verschiebt und den Vorgang k-mal wiederholt , können Sie dieses Problem leicht lösen. Dies wird jedoch mehr Zeit in Anspruch nehmen, da die zeitliche Komplexität O(k * N) beträgt.
Inversionsalgorithmus: Inversion ist die Umkehrung eines Arrays. Das Drehen eines Arrays kann durch Umkehren bestimmter Elementbereiche erfolgen. Gemäß diesem Algorithmus -
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
In diesem Artikel haben wir das Problem der Rechtsdrehung eines Arrays um k Elemente unter Verwendung eines Inversionsalgorithmus besprochen. Wir haben besprochen, was der Inversionsalgorithmus ist und wie man ihn implementiert, um dieses Problem zu lösen. Wir haben auch C++-Code besprochen, um dieses Problem zu lösen. Wir können diesen Code in jeder anderen Sprache wie C, Java, Python usw. schreiben. Ich hoffe, dieser Artikel ist hilfreich für Sie.
Das obige ist der detaillierte Inhalt vonInversionsalgorithmus für die Rechtsdrehung eines Arrays, geschrieben in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!