การสืบค้นช่วงอาเรย์สำหรับองค์ประกอบที่ความถี่เท่ากับค่าในโปรแกรม C

นี่คือปัญหาเชิงสนุกสนาน มีอาเรย์ N องค์ประกอบ ต้องทำคิวรี่ Q ดังนี้:

Q(start, end) บ่งชี้ว่าจำนวนครั้งที่ตัวเลข 'p' เกิดขึ้นเท่ากับ 'p' ครั้งจาก start ถึง end

เช่น อาเรย์ {1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8} คิวรี่:

Q(1, 8) - 1 ปรากฏ 1 ครั้ง และ 3 ปรากฏ 3 ครั้ง คำตอบคือ 2

Q(0, 2) - 1 ปรากฏ 1 ครั้ง คำตอบคือ 1

อัลกอริทึม

query(s, e) -

Begin
  get the elements and count the frequency of each element 'e' into one map
  count := count + 1
  for each key-value pair p, do
    if p.key = p.value, then
      count := count + 1
    done
    return count;
End

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

#include 
#include 
using namespace std;
int query(int start, int end, int arr[]) {
    map freq;
    for (int i = start; i <= end; i++) // รับองค์ประกอบและเก็บความถี่
        freq[arr[i]]++;
    int count = 0;
    for (auto x : freq)
        if (x.first == x.second) // เมื่อความถี่เท่ากัน เพิ่ม count
            count++;
    return count;
}
int main() {
    int A[] = {1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8};
    int n = sizeof(A) / sizeof(A[0]);
    int queries[][3] = {{ 0, 1 },
        { 1, 8 },
        { 0, 2 },
        { 1, 6 },
        { 3, 5 },
        { 7, 9 }
    };
    int query_count = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < query_count; i++) {
        int start = queries[i][0];
        int end = queries[i][1];
        cout << "Answer for Query " << (i + 1) << " = " << query(start, end, A) << endl;
    }
}

ผลลัพธ์

Answer for Query 1 = 1
Answer for Query 2 = 2
Answer for Query 3 = 1
Answer for Query 4 = 1
Answer for Query 5 = 1
Answer for Query 6 = 0