นับคู่ในอาเรย์ที่ความถี่ของหนึ่งมากกว่าหรือเท่ากับค่าของอีกตัวใน C++

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

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

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

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

คำอธิบาย − คู่ที่ถูกต้องที่ A ปรากฏ B ครั้งและ B ปรากฏ A ครั้งคือ (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

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

ในแนวทางนี้เราจะสร้างและเติมข้อมูล unordered_map ที่มีความถี่ของสมาชิกอาเรย์ จากนั้นเดินทางผ่าน unordered_map ด้วยลูป FOR สำหรับแต่ละสมาชิกและความถี่ หากพบความถี่มากกว่า ให้เพิ่มจำนวนคู่

• รับอาเรย์ arr[] ของจำนวนเต็ม
• ฟังก์ชัน frequency_other_value(int arr[], int size) รับอาเรย์และขนาด คืนจำนวนคู่ที่คู่คือ (A,B) โดย A ปรากฏอย่างน้อย B ครั้งและในทางกลับกัน
• กำหนด count เริ่มต้นเป็น 0
• สร้าง unordered_map<int, int> um สำหรับสมาชิกของ arr[] และความถี่
• เดินทางผ่านแมปด้วยลูป FOR สำหรับค่าแรกของคู่ start=it.second (it=iterator) เดินทางผ่านแมปสำหรับความถี่ >= start ด้วยลูป FOR
• เพิ่ม count สำหรับคู่ดังกล่าว
• คืน count เป็นผลลัพธ์

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

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

int frequency_other_value(int arr[], int len){
    int count = 0;
    unordered_map<int, int> um;
    for (int i = 0; i < len; ++i){
        um[arr[i]]++;
    }
    for (auto it : um){
        int start = it.first;
        int end = it.second;
        for (int j = 1; j <= end; j++){
            if (um[j] >= start){
                count++;
            }
        }
    }
    return count;
}

int main(){
    int arr[] = { 3, 3, 3, 5, 5, 6, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs in an array such that frequency of one is at least value of other are: "<<frequency_other_value(arr, size);
    return 0;
}

เอาต์พุต

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

Count of pairs in an array such that frequency of one is at least value of other are: 1