ค้นหาจำนวนคู่ที่ไม่ซ้ำในอาร์เรย์โดยใช้ C++

เราต้องการความรู้ที่เหมาะสมเพื่อสร้างคู่ที่ไม่ซ้ำกันหลายคู่ในไวยากรณ์อาร์เรย์ใน C ++ ในการค้นหาจำนวนคู่ที่ไม่ซ้ำ เรานับคู่ที่ไม่ซ้ำทั้งหมดในอาร์เรย์ที่กำหนด นั่นคือ คู่ที่เป็นไปได้ทั้งหมดสามารถเกิดขึ้นได้ โดยที่แต่ละคู่ควรไม่ซ้ำกัน ตัวอย่างเช่น −

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

แนวทางในการหาทางออก

แนวทางแก้ไขปัญหานี้มีอยู่สองแนวทางด้วยกันคือ -

แนวทางกำลังเดรัจฉาน

ในแนวทางนี้ เราจะสำรวจผ่านแต่ละคู่ที่เป็นไปได้ เพิ่มคู่เหล่านั้นไปยังเซต และสุดท้ายหาขนาดของเซต ความซับซ้อนของเวลาของวิธีการนี้คือ O(n2 log n)

ตัวอย่าง

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

ผลลัพธ์

Number of unique pairs : 16

คำอธิบายของโค้ดด้านบน

ในโค้ดนี้ ขั้นแรก เราประกาศตัวแปรชุด จากนั้นใช้สองลูป เรากำลังสำรวจผ่านแต่ละคู่ที่เป็นไปได้ และแทรกแต่ละคู่ในชุดโดยใช้ i และ j จากนั้นเรากำลังคำนวณขนาดของชุดและพิมพ์ผลลัพธ์

แนวทางที่มีประสิทธิภาพ

อีกวิธีหนึ่งคือการหาจำนวนตัวเลขที่ไม่ซ้ำในอาร์เรย์ก่อน ตอนนี้ ทุกองค์ประกอบที่ไม่ซ้ำ รวมถึงตัวมันเอง อาจสร้างคู่กับองค์ประกอบที่ไม่ซ้ำอื่น ๆ ดังนั้นจำนวนของคู่ที่ไม่ซ้ำจะเท่ากับกำลังสองของจำนวนของตัวเลขที่ไม่ซ้ำทั้งหมด ความซับซ้อนของเวลาของวิธีการของเขาคือ O(n)

ตัวอย่าง

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

ผลลัพธ์

Number of unique pairs : 16

คำอธิบายของโค้ดด้านบน

ในโค้ดนี้ เราประกาศชุดแล้วดำเนินการผ่านแต่ละองค์ประกอบของอาร์เรย์ที่แทรกทุกองค์ประกอบในชุด หลังจากนั้นเราคำนวณขนาดของชุดและพบผลลัพธ์จากสูตร n2 และพิมพ์ผลลัพธ์ออกมา

บทสรุป

ในบทความนี้ เราแก้ปัญหาในการค้นหาจำนวนคู่ที่ไม่ซ้ำในอาร์เรย์ที่เราพูดถึงสองวิธีในการแก้ปัญหา นั่นคือ ง่ายและมีประสิทธิภาพ ด้วยวิธีง่ายๆ เราแทรกคู่ที่เป็นไปได้ทั้งหมดในชุดที่มีความซับซ้อนของเวลาเป็น O(n2 log n) และในแนวทางที่มีประสิทธิภาพ เราจะค้นหาตัวเลขที่ไม่ซ้ำกันทั้งหมดและค้นหาผลลัพธ์ด้วย n2 เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ หวังว่าบทความนี้จะเป็นประโยชน์