หาความถี่ของแต่ละองค์ประกอบในอาร์เรย์ช่วงจำกัดในเวลาน้อยกว่า O(n) ด้วย C++

สมมติว่ามีอาร์เรย์ของจำนวนเต็ม อาร์เรย์คือ A และขนาดคือ n งานของเราคือการหาความถี่ของทุกองค์ประกอบในอาร์เรย์ในเวลาน้อยกว่า O(n) ขนาดขององค์ประกอบต้องน้อยกว่าค่าใดค่าหนึ่ง คือ M ที่นี่เราจะใช้วิธีการค้นหาแบบทวิภาค (Binary Search) เราจะแบ่งอาร์เรย์ออกเป็นสองส่วนอย่างเรียกซ้ำหากองค์ประกอบปลายทางต่างกัน หากองค์ประกอบปลายทางทั้งสองเหมือนกัน แสดงว่าองค์ประกอบทั้งหมดในอาร์เรย์เหมือนกัน เนื่องจากอาร์เรย์ถูกเรียงลำดับไว้แล้ว

ตัวอย่าง

#include <iostream> 
#include <vector> 
using namespace std; 

void calculateFreq(int arr[], int left, int right, vector<int>& frequency) {
    if (arr[left] == arr[right])
        frequency[arr[left]] += right - left + 1;
    else {
        int mid = (left + right) / 2;
        calculateFreq(arr, left, mid, frequency);
        calculateFreq(arr, mid + 1, right, frequency);
    }
}

void getAllFrequency(int arr[], int n) {
    vector<int> frequency(arr[n - 1] + 1, 0);
    calculateFreq(arr, 0, n - 1, frequency);
    for (int i = 0; i <= arr[n - 1]; i++)
        if (frequency[i] != 0)
            cout << "Frequency of element " << i << " is " << frequency[i] << endl;
}

int main() {
    int arr[] = { 10, 10, 10, 20, 30, 30, 50, 50, 80, 80, 80, 90, 90, 99 };
    int n = sizeof(arr) / sizeof(arr[0]);
    getAllFrequency(arr, n);
}

ผลลัพธ์

Frequency of element 10 is 3
Frequency of element 20 is 1
Frequency of element 30 is 2
Frequency of element 50 is 2
Frequency of element 80 is 3
Frequency of element 90 is 2
Frequency of element 99 is 1