Trouver le nombre de paires uniques dans un tableau en utilisant C++

Nous avons besoin de connaissances appropriées pour créer plusieurs paires uniques dans la syntaxe des tableaux en C++. Tout en trouvant le nombre de paires uniques, nous comptons toutes les paires uniques dans le tableau donné, c'est-à-dire que toutes les paires possibles peuvent être formées où chaque paire doit être unique. Par exemple -

Input : array[ ] = { 5, 5, 9 }
Output : 4
Explanation : The number of all unique pairs are (5, 5), (5, 9), (9, 5) and (9, 9).

Input : array[ ] = { 5, 4, 3, 2, 2 }
Output : 16

Façons de trouver une solution

Il existe deux façons de résoudre ce problème, ce sont les suivantes : −

Méthode par force brute

Dans cette méthode, nous allons parcourir toutes les paires possibles en ajoutant ces paires à Dans une collection, enfin trouver la taille de la collection. La complexité temporelle de cette méthode est O(n2 log n).

Exemple

#include <bits/stdc++.h>
using namespace std;
int main () {
   int arr[] = { 5, 4, 3, 2, 2 };
   int n = sizeof (arr) / sizeof (arr[0]);
   // declaring set to store pairs.
   set < pair < int, int >>set_of_pairs;

   for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
         set_of_pairs.insert (make_pair (arr[i], arr[j]));

   int result = set_of_pairs.size();

   cout <<"Number of unique pairs : " << result;
   return 0;
}

Output

Number of unique pairs : 16

Explication du code ci-dessus

Dans ce code, nous déclarons d'abord une variable définie, puis utilisons deux boucles pour parcourir chaque paire d'éléments possible et convertir chaque paire en utilisant i et j. Les éléments sont inséré dans la collection. Ensuite, nous calculons la taille de la collection et imprimons le résultat.

Méthode efficace

Une autre façon consiste d'abord à connaître le nombre de nombres uniques dans le tableau ; maintenant, en dehors de lui-même, chaque autre élément unique peut créer une paire avec n'importe quel autre élément unique, donc le nombre de paires uniques est égal à le carré de tous les nombres uniques. La complexité temporelle de cette méthode est O(n).

Exemple

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

int main () {
   int arr[] = { 5, 4, 3, 2, 2 };
   int n = sizeof (arr) / sizeof (arr[0]);

   // declaring set to store unique elements.

   unordered_set < int >set_of_elements;
   // inserting elements in the set.
   for (int i = 0; i < n; i++)
      set_of_elements.insert (arr[i]);

   int size = set_of_elements.size ();
   // finding number of unique pairs
   int result = size * size;

   cout << "Number of unique pairs in an array: " << result;
   return 0;
}

Output

Number of unique pairs : 16

Explication du code ci-dessus

Dans ce code, nous déclarons une collection, puis parcourons chaque élément du tableau et insérons chaque élément dans la collection. Après cela, nous avons calculé la taille de l'ensemble, trouvé le résultat selon la formule n2 et imprimé le résultat.

Conclusion

Dans cet article, nous avons résolu le problème de la recherche de logarithmes uniques dans un tableau et discuté de deux solutions, simples et efficaces. Dans l'approche simple, nous insérons toutes les paires possibles dans l'ensemble avec une complexité temporelle O(n2 log n), tandis que dans l'approche efficace, nous trouvons tous les nombres uniques et trouvons le résultat par n2. Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et autres. J'espère que cet article vous sera 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!