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
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.
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.
Geben Sie ein Array ganzzahliger Elemente ein, berechnen Sie die Arraygröße
Interne Neuordnung der Funktion ( arr, size)#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; }
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!