Maison >développement back-end >C++ >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.
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
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.
#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; }
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!