องค์ประกอบอาร์เรย์ที่มีความถี่เฉพาะ?

สมมติว่าเรามีหนึ่งอาร์เรย์ เราต้องนับจำนวนองค์ประกอบที่มีอยู่ในอาร์เรย์จำนวนเฉพาะของจำนวนครั้ง ดังนั้นหากอาร์เรย์คือ {1, 2, 2, 0, 1, 5, 2, 5, 0, 0, 1, 1} แล้ว 1 มีอยู่ 4 ครั้ง 2 มีอยู่ 3 ครั้ง 0 มีอยู่ 3 ครั้ง และ 5 มีอยู่ 2 ครั้ง ดังนั้น มีสามองค์ประกอบ {2, 0, 5} ที่เกิดขึ้นเป็นจำนวนเฉพาะ นับเป็น 3

อัลกอริทึม

countPrimeOccurrence(arr, n)

Begin
   count := 0
   define map with int type key and int type value
   for each element e in arr, do
      increase map.key(arr).value
   done
   for each key check whether the value corresponding the value is prime or not, if prime, then increase count.
   return count
End

ตัวอย่าง

#include <iostream>
#include <map>
using namespace std;
bool isPrime(int n){
   for(int i = 2; i<=n/2; i++){
      if(n % i == 0){
         return false;
      }
   }
   return true;
}
int countPrimeOcurrence(int arr[], int n){
   int count = 0;
   map<int, int> freq_map;
   for(int i = 0; i<n; i++){
      freq_map[arr[i]]++; //increase the frequency
   }
   for (auto it = freq_map.begin(); it != freq_map.end(); it++) {
      if (isPrime(it->second))
         count++;
   }
   return count;
}
int main() {
   int arr[] = {1, 2, 2, 0, 1, 5, 2, 5, 0, 0, 1, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Prime frequency count: " << countPrimeOcurrence(arr, n);
}

ผลลัพธ์

Prime frequency count: 3