En C++, utilisez l'espace supplémentaire O(1) pour réorganiser un tableau afin que les éléments positifs et négatifs alternent

Nous obtenons un tableau de type entier contenant des nombres positifs et négatifs, disons, arr[] de n'importe quelle taille donnée. La tâche consiste à réorganiser un tableau de manière à ce que les nombres positifs soient entourés de nombres négatifs. S'il y avait plus de positivité et Les nombres négatifs seront triés à la fin du tableau.

Regardons différentes situations d'entrée et de sortie −

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

Output − Tableau avant tri : -1 -2 -3 1 2 3 Réorganiser un tableau de manière à ce que les éléments positifs et négatifs alternent et ne nécessitent pas d'espace supplémentaire est : -1 1 -2 2 -3 3.

Explication : Étant donné un tableau entier de taille 6 contenant des éléments positifs et négatifs. Nous allons maintenant réorganiser le tableau afin que tous les éléments positifs apparaissent avant les éléments négatifs sans nécessiter d'espace supplémentaire. Entouré d'éléments négatifs et de tous les éléments supplémentaires, -1 1 -2 2 -3 3 sera ajouté à la fin du tableau final, qui est le résultat final.

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

Output - avant de trier le tableau : -1 -2 -3 1 2 3 5 5 -5 3 1 1 La complexité temporelle de la réorganisation du tableau en alternant termes positifs et négatifs sans utiliser d'espace supplémentaire est O(1) : -1 1 -2 2 -3 3 -5 5 5 3 1 1

Explication - Nous donnons un Un entier tableau de taille 12 contenant des éléments positifs et négatifs. Maintenant, nous allons réorganiser le tableau de telle manière que tous les éléments positifs soient entourés d'éléments négatifs et ajouter tous les éléments supplémentaires à la fin du tableau, c'est-à-dire -1 1 -2 2 -3 3 -5 5 5 3 1 1 sera le résultat final.

La méthode utilisée dans le programme ci-dessous est la suivante

• Saisissez un tableau de type entier et calculez la taille du tableau.

• Utilisez une boucle FOR pour imprimer le tableau avant d'effectuer l'opération de réorganisation.

• Appelez la fonction Rearrangement(arr, size) en passant le tableau et la taille du tableau comme paramètres.

• Dans la fonction Rearrangement(arr, size)

  • déclarez une variable entière 'ptr' et initialisez-la à -1.

  • Boucle de i à 0 jusqu'à ce que i soit inférieur à la taille. À l'intérieur de la boucle, vérifiez si ptr est supérieur à 0, puis vérifiez si arr[i] est supérieur à 0 et arr[ptr] est inférieur à 0 ou arr[i] est inférieur à 0 et arr[ptr] est supérieur à 0 , puis appelez la fonction move_array(arr, size, ptr, i), et vérifie si i - ptr est supérieur à 2, puis définit ptr sur ptr + 2. Sinon, définissez ptr sur -1.

  • Vérifiez si ptr est égal à -1, puis vérifiez que arr[i] est supérieur à 0 et !(i & 0x01) ou (arr[i] est inférieur à 0) et (i & 0x01), puis définissez ptr à moi.

• À l'intérieur de la fonction move_array(int arr[], int size, int ptr, int temp)

  • déclarez une variable de type caractère nommée 'ch' et définissez-la sur arr[temp] .

  • Boucle de i à temp jusqu'à ce que i soit supérieur à ptr. À l'intérieur de la boucle, définissez arr[i] sur arr[i - 1].

  • Réglez arr[ptr] sur ch.

Exemple

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

Output

Si nous exécutons le code ci-dessus, il générera la sortie suivante

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!