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

เราต้องการความรู้ที่เหมาะสมในการสร้างคู่ที่ไม่ซ้ำกันในอาร์เรย์ด้วยภาษา C++ ในการหาจำนวนคู่ที่ไม่ซ้ำกัน เรานับคู่ทั้งหมดที่เป็นไปได้จากอาร์เรย์ที่กำหนด โดยแต่ละคู่ต้องไม่ซ้ำกัน เช่น -

Input : array[ ] = { 5, 5, 9 } Output : 4 Explanation : คู่ที่ไม่ซ้ำกันคือ (5, 5), (5, 9), (9, 5) และ (9, 9)
Input : array[ ] = { 5, 4, 3, 2, 2 } Output : 16

วิธีการแก้ปัญหา

มีสองวิธีแก้ปัญหานี้ คือ

วิธี Brute Force

วนลูปผ่านทุกคู่ที่เป็นไปได้ เพิ่มคู่เหล่านั้นลงใน Set แล้วหาขนาดของ Set ความซับซ้อนด้านเวลา O(n² 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]); 
    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

คำอธิบายโค้ด

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

วิธีมีประสิทธิภาพ (Efficient Approach)

หาจำนวนสมาชิกที่ไม่ซ้ำกันในอาร์เรย์ก่อน ทุกสมาชิกที่ไม่ซ้ำกันสามารถจับคู่กับสมาชิกที่ไม่ซ้ำกันอื่นๆ รวมถึงตัวเองได้ ดังนั้นจำนวนคู่ที่ไม่ซ้ำกัน = จำนวนสมาชิกที่ไม่ซ้ำกัน² ความซับซ้อนด้านเวลา 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]); 
    unordered_set < int > set_of_elements; 
    for (int i = 0; i < n; i++) 
        set_of_elements.insert (arr[i]); 
    int size = set_of_elements.size (); 
    int result = size * size; 
    cout << "Number of unique pairs in an array: " << result; 
    return 0; 
}

ผลลัพธ์

Number of unique pairs : 16

คำอธิบายโค้ด

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

สรุป

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