Umkehralgorithmus für die Array-Rotation, geschrieben in C++

In dem gegebenen Problem haben wir ein Array und müssen das Array mit einem Inversionsalgorithmus wie −

Input : arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2
Output : arr[] = [3, 4, 5, 6, 7, 1, 2]
Explanation : As you can see we have to rotate this array by d = 2 but our main task is to achieve this by using a reversal technique.

um d Elemente drehen. Wir haben einige Berechnungen zur Drehung des Arrays mit der Inversionstechnik durchgeführt und Schlussfolgerung:

Zuerst kehren wir die ersten d Elemente des Arrays um.
Zweitens invertieren wir die restlichen Elemente.
Drittens kehren wir das gesamte Array um.

Durch die Anwendung dieser drei Schritte können wir das gedrehte Array erhalten.

Lösungsmethode

In diesem Problem schreiben wir zunächst eine Funktion, die die Elemente umkehrt. Anschließend folgen wir den oben genannten Schritten.

Beispiel

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

void reverseArray(int arr[], int start, int end) { // our reversal algorithm
   while (start < end) { // if start becomes equal to end we break the loop
      int temp = arr[start];
      arr[start] = arr[end];
      arr[end] = temp;
      start++;
      end--;
   }
   return ;
}
void Rotate(int arr[], int d, int n) { // rotation function
   if (d == 0) // no rotation required
      return;
   d = d % n; // when d becomes equal to n so our array comes to its original form
   reverseArray(arr, 0, d - 1); // reversing first d elements
   reverseArray(arr, d, n - 1); // reversing the remaining elements
   reverseArray(arr, 0, n - 1); // reversing the whole array

   return ;
}
int main() {
   int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our array
   int d = 2;
   Rotate(arr, d, n);
   for(int i = 0; i < n; i++) // printing the array
      cout << arr[i] << " ";
   cout << "\n";
   return 0;
}

Ausgabe

3 4 5 6 7 1 2

Erläuterung des obigen Codes

In der obigen Methode erstellen wir zunächst eine Inversionstechnik, die drei Parameter akzeptiert, d. h. Array, Startindex und Endindex, und uns umwandelt. Das Array ist umgekehrt Startposition bis zur Endposition. Da wir den Algorithmus bereits entwickelt haben, werden wir diese Funktion verwenden, um den Algorithmus anzuwenden. Zuerst kehren wir die ersten d Elemente um. Dann kehren wir die verbleibenden Elemente um und schließlich kehren wir das gesamte Array um. Dadurch wird unser Array um d Positionen gedreht. In der Rotationsfunktion setzen wir d auf d % n. Denn wenn wir die ersten n Elemente des Arrays drehen, erhalten wir die gleiche Antwort wie zuvor, also nehmen wir d modulo n.

Fazit

In diesem Artikel haben wir ein Problem bei der Anwendung des Inversionsalgorithmus für die Array-Rotation gelöst. Wir haben auch ein C++-Programm und die vollständige (normale) Lösung dieses Problems kennengelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Ich hoffe, dieser Artikel ist hilfreich für Sie.

Das obige ist der detaillierte Inhalt vonUmkehralgorithmus für die Array-Rotation, geschrieben in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!