นับคู่ (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}

ผลผลิต − จำนวนคู่ในอาร์เรย์ที่ความถี่ของหนึ่งมีค่าอย่างน้อยของอีกคู่หนึ่งคือ − 1

คำอธิบาย คู่ที่ถูกต้องในอาร์เรย์ที่ p เกิดขึ้น q ครั้งและ q เกิดขึ้น p ครั้งคือ (3, 3), (5, 5) และ (3, 5) เนื่องจาก 3 เกิดขึ้น 5 ครั้งและ 5 เกิดขึ้น 3 ครั้งในอาร์เรย์ . ดังนั้นมีคู่ที่ถูกต้องสามคู่จึงนับเป็น 3

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

• ป้อนอาร์เรย์ขององค์ประกอบจำนวนเต็มและคำนวณขนาดของอาร์เรย์และส่งข้อมูลไปยังฟังก์ชันเพื่อการประมวลผลต่อไป

• ประกาศการนับตัวแปรชั่วคราวเพื่อเก็บการเกิดขึ้นของ p และ q

• สร้างตัวแปร vec ของประเภท vector และ um ของประเภท unordered_map

• เริ่มวนซ้ำ FOR จาก 0 ถึงขนาดของอาร์เรย์

• ภายในลูป ตั้งค่า um[arr[i]] เป็น 1 และตรวจสอบว่า um เป็น 1 หรือไม่ จากนั้นกด arr[i] ในเวกเตอร์

• เริ่มวนรอบอื่น FOR จาก 0 จนถึงขนาดของเวกเตอร์ และกาเครื่องหมาย IF um[vec[i]

• ภายในลูป j ตรวจสอบ IF um[j]>=vec[i] จากนั้นให้เพิ่มจำนวนขึ้น 1

• คืนจำนวน

• พิมพ์ผลลัพธ์

ตัวอย่าง

#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