นับคู่ (p, q) ที่ p ปรากฏในอาเรย์อย่างน้อย q ครั้ง และ q ปรากฏอย่างน้อย p ครั้งใน C++

เราได้รับอาเรย์ของจำนวนเต็มบวก เป้าหมายคือหาจำนวนคู่ของสมาชิกของ arr[] ที่คู่มีสมาชิก (p, q) โดยที่ p ปรากฏในอาเรย์อย่างน้อย q ครั้ง และ q ปรากฏในอาเรย์อย่างน้อย p ครั้ง

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

อินพุต − int arr[] = { 3, 3, 3, 5, 5, 6, 6 }

เอาต์พุต − จำนวนคู่ในอาเรย์ที่ความถี่ของหนึ่งมากกว่าหรือเท่ากับค่าของอีกตัว คือ 1

คำอธิบาย − คู่ที่ถูกต้องในอาเรย์ที่ p ปรากฏ q ครั้งและ q ปรากฏ p ครั้งคือ (3, 3) เพราะ 3 ปรากฏ 3 ครั้งในอาเรย์ มีเพียงคู่เดียวที่ถูกต้อง จำนวนคือ 1

อินพุต − int arr[] = { 3, 3, 3, 3, 3, 5, 5, 5, 6, 6 }

เอาต์พุต − จำนวนคู่ในอาเรย์ที่ความถี่ของหนึ่งมากกว่าหรือเท่ากับค่าของอีกตัว คือ 3

คำอธิบาย − คู่ที่ถูกต้องคือ (3, 3), (5, 5) และ (3, 5) เพราะ 3 ปรากฏ 5 ครั้งและ 5 ปรากฏ 3 ครั้งในอาเรย์ มีคู่ที่ถูกต้อง 3 คู่ จำนวนคือ 3

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

• รับอาเรย์จำนวนเต็มและคำนวณขนาด ส่งไปฟังก์ชันประมวลผล
• ประกาศตัวแปรชั่วคราว count เก็บจำนวนครั้งของ p และ q
• สร้างตัวแปร vec เป็น vector และ um เป็น unordered_map
• ลูป FOR จาก 0 ถึงขนาดอาเรย์
• ในลูป เพิ่ม um[arr[i]] และตรวจสอบถ้า um[arr[i]] == 1 ใส่ arr[i] เข้า vec
• ลูป FOR อีกชั้นจาก 0 ถึงขนาด vec ตรวจสอบถ้า um[vec[i]] < vec[i] ข้ามไป มิฉะนั้นถ้าเท่ากัน เพิ่ม count 1 มิฉะนั้นเพิ่ม count 1 เริ่มลูป j จาก vec[i] + 1 ถึง um[vec[i]]
• ในลูป j ตรวจสอบถ้า um[j] >= vec[i] เพิ่ม count 1
• คืนค่า count
• พิมพ์ผลลัพธ์

ตัวอย่างโค้ด C++

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

int pair_count(int arr[], int len){
    int count = 0;
    vector<int> vec;
    unordered_map<int, int> um;
    for (int i = 0; i < len; i++){
        um[arr[i]]++;
        if (um[arr[i]] == 1){
            vec.push_back(arr[i]);
        }
    }
    for (int i = 0; i < vec.size(); i++){
        if (um[vec[i]] < vec[i]){
            continue;
        } else if (um[vec[i]] == vec[i]){
            count++;
        } else {
            count++;
            for (int j = vec[i] + 1; j <= um[vec[i]]; j++){
                if (um[j] >= vec[i]){
                    count++;
                }
            }
        }
    }
    return count;
}

int main(){
    int arr[] = { 1, 1, 1, 5, 5, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: "<<pair_count(arr, size);
    return 0;
}

เอาต์พุต

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

Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: 1