โปรแกรม C++ หาสมาชิกอาร์เรย์ที่มีความถี่เป็นจำนวนเฉพาะ

อาร์เรย์ (Array) คือโครงสร้างข้อมูลที่เก็บสมาชิกชนิดเดียวกัน

ความถี่ที่เป็นจำนวนเฉพาะ (Prime Frequencies) หมายถึงจำนวนครั้งที่สมาชิกปรากฏในอาร์เรย์เป็นจำนวนเฉพาะ

โจทย์คือการหาสมาชิกในอาร์เรย์ที่มีความถี่เป็นจำนวนเฉพาะ เราได้รับสตริงของอาร์เรย์ ต้องนับความถี่ของแต่ละตัวอักษร ตรวจสอบว่าความถี่เป็นจำนวนเฉพาะหรือไม่ และนับจำนวนสมาชิกที่มีความถี่เป็นจำนวนเฉพาะ

ตัวอย่าง:

Input: str = "helloworld" Output: 2

คำอธิบาย

จำนวนครั้งที่ตัวอักษรแต่ละตัวปรากฏ:

h -> 1 e -> 1 l -> 3 o -> 2 w -> 1 r -> 1 d -> 1

ตัว 'l' ปรากฏ 3 ครั้ง (จำนวนเฉพาะ) และตัว 'o' ปรากฏ 2 ครั้ง (จำนวนเฉพาะ)

วิธีแก้: วนลูปผ่านสตริง นับความถี่แต่ละตัวอักษรด้วย map ใน C++ แล้วตรวจสอบว่าความถี่เป็นจำนวนเฉพาะ ถ้าใช่เพิ่มตัวนับ

อัลกอริทึม

ตรวจสอบความถี่ของสมาชิกว่าเป็นจำนวนเฉพาะโดยใช้ map เพื่อนับความถี่

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

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

int check_prime(int n) {
    if (n <= 1) return 0;
    if (n <= 3) return 1;
    if (n % 2 == 0 || n % 3 == 0) return 0;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    return 1;
}

int countPrimeFrequent(string s) {
    int count = 0;
    unordered_map<char, int> mp;
    for (int i = 0; i < s.length(); i++)
        mp[s[i]]++;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        if (check_prime(it->second))
            count++;
    }
    return count;
}

int main() {
    string s = "helloworld";
    cout << countPrimeFrequent(s);
    return 0;
}

ผลลัพธ์

The repeat elements of the array are : 2