Rechercher des paires de valeurs positives et négatives dans un tableau en utilisant C++

Dans cet article, nous avons un tableau avec différents éléments. Nous devons imprimer les paires de valeurs positives et négatives dans le tableau avec la même valeur absolue et les imprimer dans un ordre trié comme-

Input : arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88}
Output : -1 1 -12 12 -56 56

Input : arr[] = {30, 40, 50, 77, -51, -50, -40}
Output : -40 40 -50 50

Méthodes pour trouver la solution

La première méthode à laquelle nous avons pensé était la méthode de la force brute puis nous avons également mis au point une méthode appelée méthode à haut rendement. Nous discuterons des deux méthodes.

Méthode de force brute

Dans cette méthode, nous allons parcourir le tableau avec un indice et trouver la même valeur absolue mais un indice différent.

Exemple

#include<bits/stdc++.h>
using namespace std;

int main() {
   int arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88 };
   int n = sizeof(arr)/sizeof(int); // size of our array.
   vector<int> nums; // the present pairs.

   for(int i = 0; i < n; i++) {
      for(int j = i+1; j < n; j++) {
         if(abs(arr[j]) == abs(arr[i])) { // finding the pairs.
            nums.push_back(abs(arr[i]));
            break;
            // if we found the pair then we can just break as there are distinct elements in the array.
         }
      }
   }
   sort(nums.begin(), nums.end());
   for(auto x : nums) // printing the pairs.
      cout << -x << " " << x << " ";
}

Output

-1 1 -12 12 -56 56

Dans cette approche, nous utilisons deux boucles pour parcourir le tableau et trouver un autre élément ; si nous trouvons un autre élément, nous sortons de la boucle interne pour accélérer le code. Nous utilisons maintenant deux boucles for et la complexité temporelle globale est O(N*N). N est la taille du tableau donné, fonctionne bien pour des contraintes faibles, mais pas pour des contraintes plus élevées, nous allons donc maintenant discuter d'une autre approche.

Méthode efficace

Dans cette méthode, nous utiliserons une carte de hachage, ce qui réduira considérablement notre complexité temporelle.

Exemple

#include<bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };
   int n = sizeof(arr)/sizeof(int); // size of our array.
   map<int, int> found; // going to store the count of numbers found.
   vector<int> nums; // the present pairs.
   for(int i = 0; i < n; i++)
      found[abs(arr[i])]++; // increasing the frequency of abs(arr[i]).
   for(auto x : found) { // traversing the map.
      if(x.second == 2) // if any numbers frequency is two then push it to nums.
         nums.push_back(x.first);
   }
   for(auto x : nums) // printing the pairs.
      cout << -x << " " << x << " ";
}

Sortie

-1 1 -4 4 -8 8 -9 9

Explication du code ci-dessus

Dans cette approche, nous utilisons une table de hachage pour stocker la fréquence des nombres lorsque nous parcourons le tableau, nous mettons maintenant à jour la fréquence de la valeur absolue ; de l'élément actuel, puisque vous savez que toutes les paires ont la valeur 2, nous parcourons la carte.

Si la fréquence d'un nombre est 2, alors nous le stockons en nombres et enfin, nous imprimons les valeurs dans l'ordre trié. (Puisque la carte contient des nombres triés, nous n'avons pas besoin de trier les vecteurs numériques).

Conclusion

Dans cet article, nous avons résolu le problème de la recherche de paires de valeurs positives et négatives dans un tableau à l'aide de techniques de hachage. Nous avons également appris un programme C++ pour résoudre ce problème et une manière complète de résoudre ce problème (normale et efficace). Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que cet article vous a été utile.

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!