En C++, réorganisez les nombres positifs et négatifs en complexité temporelle O(n) et en espace supplémentaire O(1)

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 tous les nombres positifs et négatifs soient dans des positions alternées et s'il y a des nombres positifs ou négatifs supplémentaires. éléments et ils seront placés à la fin du tableau.

Voyons différents scénarios d'entrée et de sortie pour cette situation -

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

output− dans Réorganisation des valeurs positives et les nombres négatifs en temps O(n) et en temps O(1) l'espace supplémentaire est : 2 - 1 6 -1 4 -3

Explication− Nous obtenons un tableau d'entiers de taille 6 contenant des éléments positifs et négatifs. Nous allons maintenant réorganiser le tableau de manière à ce que tous les éléments positifs totalisent Les éléments négatifs sont dans des positions alternées et tous les éléments supplémentaires seront ajoutés à la fin du tableau, c'est-à-dire que 2 -1 6 -1 4 -3 sera le résultat final

input

input

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

sortie strong>− en temps O(n) et O(1) supplémentaire espace et nombres négatifs réarrangés comme : 2 - 2 3 -5 5 -3 5 -1 1 3 1 1

Explication - On obtient un tableau d'entiers de taille 12 contenant des éléments positifs et négatifs. Nous allons maintenant réorganiser le tableau de manière à ce que tous les éléments positifs et négatifs soient dans des positions alternées et que tous les éléments supplémentaires soient ajoutés à la fin du tableau, c'est-à-dire 2 -2 3 -5 5 -3 5 -1 1 3 1 1 pour la finale. Résultat

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

• Entrez les éléments d'entrée d'un tableau entier et calculez la taille du tableau.

• Imprimez le tableau avant d'effectuer l'opération de réorganisation à l'aide d'une boucle FOR.

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

• fonction Rearrangement(arr, size) en interne

  • déclare une variable entière temporaire, c'est-à-dire que temp est -1, le nombre positif est temp + 1 et le nombre négatif est 0.

  • Commencez à boucler de i à 0 jusqu'à ce que i soit inférieur à la taille du tableau. Dans la boucle, vérifiez SI arr[i] est inférieur à 0, puis incrémentez temp de 1 et appelez la méthode intégrée de C++ STL, qui est swap(arr[temp], arr[i]) et passez arr[temp ] et arr[i] comme paramètres.

  • Démarrez la boucle, TANDIS que le nombre positif est inférieur à la taille du tableau ET que le nombre négatif est inférieur au nombre positif ET que arr[nombre négatif] est inférieur à 0. Au sein de la boucle, les appels sont échangés en passant arr[negative] et arr[positive] comme arguments. Ajoute 1 aux nombres positifs et définit les nombres négatifs sur négatif + 2.

• Imprimez les résultats.

Exemple

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

Output

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

Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -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!