Heim  >  Artikel  >  Backend-Entwicklung  >  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

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

PHPz
PHPznach vorne
2023-08-28 11:53:061151Durchsuche

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

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!

Stellungnahme:
Dieser Artikel ist reproduziert unter:tutorialspoint.com. Bei Verstößen wenden Sie sich bitte an admin@php.cn löschen