นับคู่ที่ไม่ซ้ำ (arr[i], arr[j]) ที่ i < j ใน C++

เราได้รับอาเรย์ที่มีสมาชิกจำนวนเต็ม เป้าหมายคือหาคู่ที่ไม่ซ้ำของสมาชิกอาเรย์ที่คู่แบบ (arr[i],arr[j]) มีดัชนีที่ i < j

มาดูตัวอย่าง

อินพุต − arr[] = {1,2,3};

เอาต์พุต − จำนวนคู่ที่ไม่ซ้ำ (arr[i], arr[j]) ที่ i < j คือ 3

คำอธิบาย − เนื่องจากทุกสมาชิกไม่ซ้ำ คู่จะเป็น −

(1,2) - ( arr[0],arr[1] ) 0<1
(1,3) - ( arr[0], arr[2] ) 0<2
(2,3) - ( arr[1],arr[2] ) 1<2

อินพุต − arr[] = { 4,4,3,2 };

เอาต์พุต − จำนวนคู่ที่ไม่ซ้ำ (arr[i], arr[j]) ที่ i < j คือ 4

คำอธิบาย − เนื่องจากสมาชิกไม่ซ้ำ คู่จะเป็น −

(4,4) - ( arr[0],arr[1] ) 0<1
(4,3) - ( arr[0], arr[2] ) 0<2
(4,2) - ( arr[0],arr[3] ) 0<3
(3,2) - ( arr[2],arr[3] ) 2<3

แนวทางที่ใช้ในโปรแกรม

เราจะใช้สองวิธี วิธีแรกแบบง่ายด้วยลูป FOR เริ่มเดินทางอาเรย์ arr[] ด้วยลูป FOR สองชั้น จาก i=0 ถึง i<length-1 และ j=i+1 ถึง j<length ด้วยวิธีนี้จะมี i<j เสมอ ตอนนี้เพิ่มคู่ (arr[i],arr[j]) เข้า set<pair<int, int>> se ท้ายสุดขนาดของ se จะเป็นจำนวนคู่ที่ไม่ซ้ำที่มี i<j

• รับอาเรย์จำนวนเต็ม arr[] พร้อมขนาด size
• ฟังก์ชัน unique_pair(int arr[], int size) รับอาเรย์และความยาว คืนจำนวนคู่ที่ไม่ซ้ำที่ในคู่ (arr[i],arr[j]) ดัชนี i<j
• กำหนดค่าเริ่มต้นของ count เป็น 0
• สร้างเซต se ที่มีคู่จำนวนเต็ม (set<pair<int, int>> se)
• เริ่มเดินทาง arr[] ด้วยลูป FOR สองชั้น จาก i=0 ถึง i<size-1 และ j=i+1 ถึง j<size
• สำหรับแต่ละคู่ที่มี i<j เพิ่มคู่ (arr[i],arr[j]) เข้า se ด้วย se.insert(make_pair(arr[i], arr[j]))
• ท้ายสุดของลูป FOR ทั้งสอง อัปเดต count=se.size()
• count ตอนนี้มีจำนวนคู่ใน se (ทั้งหมดไม่ซ้ำ)
• คืน count

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

ในแนวทางนี้ เราจะหาสมาชิกที่ไม่ซ้ำหลังจากแต่ละสมาชิก arr[i] จะจับคู่กับสมาชิกที่แตกต่าง/ไม่ซ้ำจาก arr[i+1 ถึง size-1] ดังนั้นถ้ามี x สมาชิกไม่ซ้ำหลัง arr[i] แล้ว arr[i] จะสร้าง x คู่ เราจะสร้างอาเรย์ทำเครื่องหมายสมาชิกไม่ซ้ำหลังดัชนี i แล้วบวกจำนวนแต่ละอันเพื่อคู่ไม่ซ้ำรวม

• รับอาเรย์จำนวนเต็ม arr[] พร้อมความยาว size
• ฟังก์ชัน unique_pair(int arr[], int size) รับอาเรย์และความยาว คืนจำนวนคู่ที่ไม่ซ้ำที่ในคู่ (arr[i],arr[j]) ดัชนี i<j
• กำหนดค่าเริ่มต้นของ count เป็น 0
• ตัวแปร temp กำหนดเป็น 0
• สร้างอาเรย์ arr_2[] ความยาว size เริ่มต้น arr_2[size-1]=0 เพราะสมาชิกสุดท้ายมี 0 สมาชิกไม่ซ้ำหลังมัน
• สร้างเซตจำนวนเต็มสองตัว check และ uncheck
• เดินทางอาเรย์จากสมาชิกสุดท้ายถึงแรก i=size-1 ถึง i>=0 ค้นหา arr[i] ในเซต check
• ถ้าไม่เจอ แสดงว่าไม่ซ้ำ เพิ่ม temp (temp คือจำนวนสมาชิกไม่ซ้ำหลัง arr[i]) กำหนด arr_2[i]=temp
• มิฉะนั้น arr_2[i]=temp โดยไม่เพิ่ม temp
• เพิ่ม arr[i] เข้าเซต check ตอนนี้การเกิดครั้งต่อไปของ arr[i] จะไม่ถูกนับ
• ท้ายสุดของลูป FOR นี้ arr_2[] ถูกอัปเดต
• ตอนนี้เดินทาง arr[] จากดัชนี i=0 ถึง i<size-1 สำหรับทุก arr[i] ตรวจสอบว่าอยู่ในเซต uncheck ถ้าไม่ได้ แสดงว่า arr[i] เกิดครั้งแรก บวก arr_2[i] (สมาชิกไม่ซ้ำหลัง arr[i]) เข้า count มิฉะนั้นไม่ทำอะไรต่อ
• เพิ่ม arr[i] เข้าเซต uncheck การเกิดครั้งต่อไปจะไม่ถูกนับ
• ท้ายสุด count มีคู่ไม่ซ้ำที่ i<j สำหรับคู่ไม่ซ้ำ (arr[i],arr[j])
• คืน count

ตัวอย่าง (วิธีง่าย)

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

int unique_pair(int arr[], int size){
    int count = 0;
    set<pair<int, int>> se;
    for(int i = 0; i < (size - 1); i++){
        for (int j = i + 1; j < size; j++){
            se.insert(make_pair(arr[i], arr[j]));
        }
    }
    count = se.size();
    return count;
}

int main(){
    int arr[] = { 4, 3, 1, 6, 7 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of unique pairs (arr[i], arr[j]) such that i & j are: 10

ตัวอย่าง (แนวทางมีประสิทธิภาพ)

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

int unique_pair(int arr[], int size){
    int count = 0, temp = 0;
    int arr_2[size];
    arr_2[size-1] = 0;
    set<int> check, uncheck;
    for (int i = size - 1; i > 0; i--){
        auto set = check.find(arr[i]);
        if (set != check.end()){
            arr_2[i - 1] = temp;
        } else {
            arr_2[i - 1] = ++temp;
        }
        check.insert(arr[i]);
    }
    for (int i = 0; i < size - 1; i++){
        auto set = uncheck.find(arr[i]);
        if (set != uncheck.end()){
            continue;
        }
        count += arr_2[i];
        uncheck.insert(arr[i]);
    }
    return count;
}

int main(){
    int arr[] = { 4, 3, 1, 6, 7 };
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of unique pairs (arr[i], arr[j]) such that i < j are: 10