Ordnen Sie in C++ positive und negative Zahlen in O(n) Zeitkomplexität und O(1) zusätzlichem Speicherplatz neu an

Wir erhalten ein Array vom Typ Ganzzahl, das positive und negative Zahlen enthält, beispielsweise arr[] beliebiger Größe. Die Aufgabe besteht darin, ein Array so umzuordnen, dass sich alle positiven und negativen Zahlen an abwechselnden Positionen befinden und ob zusätzliche positive oder negative Zahlen vorhanden sind Elemente und sie werden am Ende des Arrays platziert.

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

input − int arr[] = {4, 2, -1, -1, 6, -3}

output− in Positive und neu anordnen Negative Zahlen in O(n)-Zeit und O(1)-Zeit zusätzlicher Platz ist: 2 - 1 6 -1 4 -3

Erklärung− Wir erhalten ein ganzzahliges Array der Größe 6, das positive und negative Elemente enthält. Jetzt ordnen wir das Array so um, dass sich alle positiven Elemente summieren Negative Elemente befinden sich an alternativen Positionen und alle zusätzlichen Elemente werden am Ende des Arrays hinzugefügt, d. h. 2 -1 6 -1 4 -3 wird das Endergebnis sein.

input

input

strong>− int arr [] = {- 1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}

Ausgabe strong>− in O(n) Zeit und O(1) zusätzlich Leerzeichen und negative Zahlen neu angeordnet als: 2 - 2 3 -5 5 -3 5 -1 1 3 1 1

Erklärung - Wir erhalten ein ganzzahliges Array der Größe 12, das positive und negative Elemente enthält. Jetzt ordnen wir das Array so um, dass alle positiven und negativen Elemente abwechselnd positioniert sind und alle zusätzlichen Elemente am Ende des Arrays hinzugefügt werden, d. h. 2 -2 3 -5 5 -3 5 -1 1 3 1 1 für das Finale Ergebnis

Die im folgenden Programm verwendete Methode lautet wie folgt: Geben Sie die Eingabeelemente eines ganzzahligen Arrays ein und berechnen Sie die Größe des Arrays.

• Drucken Sie das Array aus, bevor Sie den Neuanordnungsvorgang mithilfe einer FOR-Schleife durchführen.

• Rufen Sie die Funktion Rearrangement(arr, size) auf, indem Sie das Array und die Array-Größe als Parameter übergeben.

• Funktion Rearrangement(arr, size) intern

• deklariert eine temporäre Ganzzahlvariable, d. h. temp ist -1, positive Zahl ist temp + 1 und negative Zahl ist 0.

  • Beginnen Sie mit der Schleife von i bis 0, bis i kleiner als die Größe des Arrays ist. Überprüfen Sie innerhalb der Schleife, ob arr[i] kleiner als 0 ist, erhöhen Sie dann temp um 1 und rufen Sie die integrierte Methode von C++ STL auf, nämlich swap(arr[temp], arr[i]) und übergeben Sie arr[temp ] und arr[i] als Parameter.

  • Schleife starten, WÄHREND die positive Zahl kleiner als die Array-Größe ist UND die negative Zahl kleiner als die positive Zahl ist UND arr[negative Zahl] kleiner als 0 ist. Innerhalb der Schleife werden Aufrufe ausgetauscht, indem arr[negative] und arr[positive] als Argumente übergeben werden. Addiert positive Zahlen zu 1 und negative Zahlen zu negativ + 2.

  Drucken Sie die Ergebnisse aus.

• Beispiel

  #include <bits/stdc++.h>
  using namespace std;
  void Rearrangement(int arr[], int size){
     int temp = -1;
     for(int i = 0; i < size; i++){
        if (arr[i] < 0){
           temp++;
           swap(arr[temp], arr[i]);
        }
     }
     int positive = temp + 1;
     int negative = 0;
     while(positive < size && negative < positive && arr[negative] < 0){
        swap(arr[negative], arr[positive]);
        positive++;
        negative = negative + 2;
     }
  }
  int main(){
     int arr[] = {4, 2, -1, -1, 6, -3};
     int size = sizeof(arr)/sizeof(arr[0]);
     //calling the function to rearrange the array
     Rearrangement(arr, size);
     //print the array after rearranging the values
     cout<<"Rearrangement of positive and negative numbers in O(n) time and 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

Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3

Das obige ist der detaillierte Inhalt vonOrdnen Sie in C++ positive und negative Zahlen in O(n) Zeitkomplexität und O(1) zusätzlichem Speicherplatz neu an. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!