Rumah >pembangunan bahagian belakang >C++ >Cari bilangan pasangan unik dalam tatasusunan menggunakan C++

Cari bilangan pasangan unik dalam tatasusunan menggunakan C++

WBOY
WBOYke hadapan
2023-09-07 11:53:09533semak imbas

Cari bilangan pasangan unik dalam tatasusunan menggunakan C++

Kami memerlukan pengetahuan yang betul untuk mencipta beberapa pasangan unik dalam sintaks tatasusunan dalam C++. Semasa mencari bilangan pasangan unik, kami mengira semua pasangan unik dalam tatasusunan yang diberikan iaitu semua pasangan yang mungkin boleh dibentuk di mana setiap pasangan harus unik. Sebagai contoh -

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

Cara untuk mencari penyelesaian

Terdapat dua cara untuk menyelesaikan masalah ini, iaitu −

Kaedah brute force

Dalam kaedah ini, kami akan mengulangi setiap pasangan yang mungkin menambah pasangan ini ke Dalam koleksi, akhirnya cari saiz koleksi. Kerumitan masa kaedah ini ialah O(n2 log n).

Contoh

#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

Penjelasan kod di atas

Dalam kod ini, mula-mula kita mengisytiharkan pembolehubah yang ditetapkan dan kemudian menggunakan dua gelung untuk mengulangi setiap pasangan elemen yang mungkin dan menukar setiap pasangan menggunakan i dan j Elements are dimasukkan ke dalam koleksi. Kemudian kami mengira saiz koleksi dan mencetak hasilnya.

Kaedah yang cekap

Cara lain ialah dengan terlebih dahulu mengetahui bilangan nombor unik dalam tatasusunan sekarang, selain daripada dirinya sendiri, setiap elemen unik lain boleh mencipta pasangan dengan mana-mana elemen unik lain, jadi bilangan pasangan unik Sama dengan; kuasa dua semua nombor unik. Kerumitan masa kaedah ini ialah O(n).

Contoh

#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

Penjelasan kod di atas

Dalam kod ini, kami mengisytiharkan koleksi dan kemudian melelang melalui setiap elemen tatasusunan dan memasukkan setiap elemen ke dalam koleksi. Selepas itu, kami mengira saiz set dan mendapati hasilnya mengikut formula n2 dan mencetak output.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah mencari logaritma unik dalam tatasusunan dan membincangkan dua penyelesaian, mudah dan cekap. Dalam pendekatan mudah kami memasukkan semua pasangan yang mungkin ke dalam set dengan kerumitan masa O(n2 log n), manakala dalam pendekatan cekap kami mencari semua nombor unik dan mencari hasilnya dengan n2. Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan lain-lain. Semoga artikel ini membantu anda.

Atas ialah kandungan terperinci Cari bilangan pasangan unik dalam tatasusunan menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Artikel ini dikembalikan pada:tutorialspoint.com. Jika ada pelanggaran, sila hubungi admin@php.cn Padam