Ordnen Sie ein Array neu an, sodass „arr' zu „arr' wird, und verwenden Sie nur O(1) zusätzlichen Speicherplatz, der in C++ implementiert ist

Wir erhalten ein Array vom Typ positiver Ganzzahl, beispielsweise arr[] beliebiger Größe, sodass der Elementwert im Array größer als 0, aber kleiner als die Größe des Arrays sein sollte. Die Aufgabe besteht darin, neu zu ordnen Ein Array, das arr[i] nur im angegebenen O(1)-Raum in arr[arr[i]] umwandelt und das Endergebnis ausgibt.

Sehen wir uns verschiedene Ein- und Ausgabeszenarien für diese Situation an −

input− int arr[] = {0 3 2 1 5 4 }

output− Array vor dem Sortieren: 0 3 2 1 5 4 Ordnen Sie das Array so um, dass arr[i] zu arr[arr[i]] wird, mit O(1) zusätzlichem Platz: 0 1 2 3 4 5

Erklärung− Wir erhalten ein ganzzahliges Array der Größe 6 und alle Elemente im Array haben Werte kleiner als 6. Jetzt werden wir das Array neu anordnen, sodass arr[arr[0] 0 ist, arr[arr[1]] 1 ist, arr[arr [2]] 2 ist, arr[arr[3]] 3 ist, arr[ arr[4]] ist 4, arr[arr[5]] ist 5. Daher ist das endgültige Array nach der Neuanordnung 0 1 2 3 4 5.

input− int arr[] = {1, 0}

output− Array vor der Permutation: 1 0 Ordnen Sie das Array neu an, sodass arr[i] zu arr[arr[i]] wird, wobei O(1) zusätzlicher Platz ist: 0 1

Erklärung – Wir erhalten eine Ganzzahl der Größe 2 und alle Elemente im Array haben Werte ​​weniger als Array von 2. Jetzt werden wir das Array neu anordnen, sodass arr[arr[0] 1 und arr[arr[1]] 0 ist. Daher ist das endgültige Array nach der Neuanordnung 0 1.

Input− int arr[] = {1, 0, 2, 3}

Output−Array vor dem Sortieren: 1 0 2 3 Ordnen Sie das Array so um, dass arr[i] zu arr[arr[i]] wird, mit O(1) zusätzlichem Platz: 0 1 2 3

Erklärung – Wir erhalten ein Array von Ganzzahlen der Größe 4 und das Array Alle Elemente in einen Wert kleiner als 4 haben. Jetzt werden wir das Array neu anordnen, sodass arr[arr[0] 0 ist, arr[arr[1]] 1 ist, arr[arr[2] ]] 2 ist und arr[arr[3]] 3 ist. Daher ist das endgültige Array nach der Neuanordnung 0 1 2 3.

Die im folgenden Programm verwendete Methode lautet wie folgt:

• Geben Sie ein Array ganzzahliger Elemente ein, berechnen Sie die Arraygröße

  Interne Neuordnung der Funktion ( arr, size)

• Beginne eine FOR-Schleife von i nach 0, bis i kleiner als size ist. Setzen Sie innerhalb der Schleife temp auf arr[arr[i]] % size und arr[i] += temp * size.

• Beginnen Sie mit der FOR-Schleife von i nach 0, bis i kleiner als die Größe ist. Setzen Sie innerhalb der Schleife arr[i] = arr[i] / size

  • , um das Ergebnis zu drucken.

  Beispiel

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
   for(int i=0; i < size; i++){
      int temp = arr[arr[i]] % size;
      arr[i] += temp * size;
   }
   for(int i = 0; i < size; i++){
      arr[i] = arr[i] / size;
   }
}
int main(){
   //input an array
   int arr[] = {0, 3, 2, 1, 5, 4};
   int size = sizeof(arr) / sizeof(arr[0]);
   //print the original Array
   cout<<"Array before Arrangement: ";
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"\nRearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

Nach dem Login kopieren
• Ausgabe
  Wenn wir den obigen Code ausführen, wird die folgende Ausgabe generiert

Array before Arrangement: 0 3 2 1 5 4
Rearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: 0 1 2 3 4 5

Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonOrdnen Sie ein Array neu an, sodass „arr' zu „arr' wird, und verwenden Sie nur O(1) zusätzlichen Speicherplatz, der in C++ implementiert ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!