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 }

Wie man die Lösung findet

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 -

• Kehren Sie zunächst das gesamte Array um.
• Ändern Sie k modulo k modulo N (Array-Größe), da k größer als N ist.
• Kehren Sie die ersten k Elemente des Arrays um, um sie in die richtige Reihenfolge zu bringen.
• Dann kehren Sie den Bereich der restlichen Elemente um, also von k bis N-1.
• li>

Beispiel

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

Ausgabe

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

Fazit

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!