Verwenden Sie in C++ den zusätzlichen Platz O(1), um ein Array neu anzuordnen, sodass sich positive und negative Elemente abwechseln

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 positive Zahlen von negativen Zahlen umgeben sind. Wenn es mehr Positivität gäbe und Negative Zahlen werden am Ende des Arrays sortiert.

Lassen Sie uns verschiedene Eingabe- und Ausgabesituationen betrachten −

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

Output − Array vor dem Sortieren: - 1 -2 -3 1 2 3 Das Neuanordnen eines Arrays, sodass sich positive und negative Elemente abwechseln und kein zusätzlicher Platz erforderlich ist, lautet: -1 1 -2 2 -3 3.

Erklärung: Gegeben sei ein ganzzahliges Array der Größe 6, das positive und negative Elemente enthält. Jetzt ordnen wir das Array so um, dass alle positiven Elemente vor den negativen Elementen erscheinen, ohne dass zusätzlicher Platz benötigt wird Umgeben von negativen Elementen und allen zusätzlichen Elementen wird -1 1 -2 2 -3 3 am Ende des endgültigen Arrays hinzugefügt, was das Endergebnis darstellt.

Eingabe – int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1};

Ausgabe – vor dem Sortieren des Arrays : -1 -2 -3 1 2 3 5 5 -5 3 1 1 Die zeitliche Komplexität der Neuanordnung des Arrays durch Abwechseln positiver und negativer Terme ohne zusätzlichen Platzbedarf beträgt O(1): -1 1 -2 2 -3 3 -5 5 5 3 1 1

Erklärung – Wir geben eine ganze Zahl an Array der Größe 12, das positive und negative Elemente enthält. Jetzt ordnen wir das Array so um, dass alle positiven Elemente von negativen Elementen umgeben sind und fügen alle zusätzlichen Elemente am Ende des Arrays hinzu, d. h. -1 1 -2 2 -3 3 -5 5 5 3 1 1 wird das sein Endergebnis.

Die im folgenden Programm verwendete Methode lautet wie folgt:

• Geben Sie ein Array vom Typ Integer ein und berechnen Sie die Größe des Arrays.

• Verwenden Sie eine FOR-Schleife, um das Array zu drucken, bevor Sie den Neuanordnungsvorgang durchführen.

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

• Innerhalb der Funktion Rearrangement(arr, size)

  • deklarieren Sie eine ganzzahlige Variable „ptr“ und initialisieren Sie sie auf -1.

  • Schleife von i nach 0, bis i kleiner als die Größe ist. Überprüfen Sie innerhalb der Schleife, ob ptr größer als 0 ist, und prüfen Sie dann, ob arr[i] größer als 0 und arr[ptr] kleiner als 0 ist oder ob arr[i] kleiner als 0 ist und arr[ptr] größer als 0 ist , rufen Sie dann die Funktion move_array(arr, size, ptr, i) auf und prüfen Sie, ob i - ptr größer als 2 ist, und setzen Sie dann ptr auf ptr + 2. Andernfalls setzen Sie ptr auf -1.

  • Überprüfen Sie, ob ptr gleich -1 ist, und überprüfen Sie dann, ob arr[i] größer als 0 ist und !(i & 0x01) oder (arr[i] kleiner als 0 ist) und (i & 0x01). setze ptr auf i.

• Innerhalb der Funktion move_array(int arr[], int size, int ptr, int temp)

  • deklarieren Sie eine Zeichentypvariable mit dem Namen „ch“ und setzen Sie sie auf arr[temp] .

  • Schleife von i zu temp, bis i größer als ptr ist. Setzen Sie innerhalb der Schleife arr[i] auf arr[i - 1].

  • Setze arr[ptr] auf ch.

Beispiel

#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
   char ch = arr[temp];
   for(int i = temp; i > ptr; i--){
      arr[i] = arr[i - 1];
   }
   arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
   int ptr = -1;
   for(int i = 0; i < size; i++){
      if (ptr >= 0){
         if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
            move_array(arr, size, ptr, i);
            if(i - ptr >= 2){
               ptr = ptr + 2;
            }
            else{
               ptr = -1;
            }
         }
      }
      if(ptr == -1){
         if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
            ptr = i;
         }
      }
   }
}
int main(){
   //input an array
   int arr[] = {-1, -2, -3, 1, 2, 3};
   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 in alternating positive & negative items 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: -1 -2 -3 1 2 3
Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3

Das obige ist der detaillierte Inhalt vonVerwenden Sie in C++ den zusätzlichen Platz O(1), um ein Array neu anzuordnen, sodass sich positive und negative Elemente abwechseln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!