Ermitteln Sie mit C++ die Anzahl eindeutiger Paare in einem Array

Wir benötigen entsprechende Kenntnisse, um in C++ mehrere eindeutige Paare in der Array-Syntax zu erstellen. Während wir die Anzahl der eindeutigen Paare ermitteln, zählen wir alle eindeutigen Paare im angegebenen Array, d. h. alle möglichen Paare können gebildet werden, wobei jedes Paar eindeutig sein sollte. Zum Beispiel –

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

Möglichkeiten, eine Lösung zu finden

Es gibt zwei Möglichkeiten, dieses Problem zu lösen: Finden Sie die Größe der Sammlung. Die zeitliche Komplexität dieser Methode beträgt O(n2 log n).

Beispiel

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

Ausgabe

Number of unique pairs : 16

Erklärung des obigen Codes

In diesem Code deklarieren wir zunächst eine Set-Variable und verwenden dann zwei Schleifen, um jedes mögliche Elementpaar zu durchlaufen und jedes Paar mithilfe von i und j zu konvertieren. Elemente sind in die Sammlung eingefügt. Dann berechnen wir die Größe der Sammlung und drucken das Ergebnis aus.

Effiziente Methode

Eine andere Möglichkeit besteht darin, zunächst die Anzahl der eindeutigen Zahlen im Array herauszufinden. Abgesehen von sich selbst kann jedes andere eindeutige Element ein Paar mit jedem anderen eindeutigen Element bilden, sodass die Anzahl der eindeutigen Paare gleich ist das Quadrat aller eindeutigen Zahlen. Die zeitliche Komplexität dieser Methode beträgt O(n).

Beispiel

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

Ausgabe

Number of unique pairs : 16

Erklärung des obigen Codes

In diesem Code deklarieren wir eine Sammlung, durchlaufen dann jedes Element des Arrays und fügen jedes Element in die Sammlung ein. Danach haben wir die Größe der Menge berechnet, das Ergebnis gemäß der Formel n2 ermittelt und die Ausgabe gedruckt.

Fazit

In diesem Artikel haben wir das Problem gelöst, eindeutige Logarithmenpaare in einem Array zu finden, und zwei Lösungen diskutiert, nämlich einfache und effiziente. Beim einfachen Ansatz fügen wir alle möglichen Paare mit der Zeitkomplexität O(n2 log n) in die Menge ein, während wir beim effizienten Ansatz alle eindeutigen Zahlen finden und das Ergebnis anhand von n2 ermitteln. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, Sie finden diesen Artikel hilfreich.

Das obige ist der detaillierte Inhalt vonErmitteln Sie mit C++ die Anzahl eindeutiger Paare in einem Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!