นับคู่ในอาร์เรย์โดยที่ความถี่ของหนึ่งมีค่าอย่างน้อยของอีกคู่หนึ่งใน 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}

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

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

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

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

• หาอาร์เรย์ arr[] ของจำนวนเต็ม

• ฟังก์ชัน frequency_other_value(int arr[], int size) ใช้อาร์เรย์และขนาดของอาร์เรย์ และส่งคืนค่าจำนวนคู่เพื่อให้เป็นคู่ (A,B) โดยที่ A เกิดขึ้นอย่างน้อย B ครั้งและในทางกลับกัน

• นับเริ่มต้นเป็น 0

• ใช้ unordered_map um สำหรับองค์ประกอบของ arr[] และความถี่

• สำรวจแผนที่โดยใช้ for และ สำหรับค่าแรกแต่ละค่าของคู่ start=it.second; (มัน=ตัววนซ้ำ) สำรวจแผนที่สำหรับความถี่>=เริ่มใช้สำหรับวนซ้ำ

• จำนวนที่เพิ่มขึ้นสำหรับคู่ดังกล่าว

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

#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