ধরুন আমাদের পূর্ণসংখ্যার একটি অ্যারে আছে। অ্যারে হল A, এবং আকার হল n। আমাদের কাজ হল O(n) সময়ের চেয়ে কম অ্যারের সমস্ত উপাদানের ফ্রিকোয়েন্সি খুঁজে বের করা। এলিমেন্টের সাইজ অবশ্যই এক মানের থেকে কম হওয়া উচিত M. এখানে আমরা বাইনারি অনুসন্ধান পদ্ধতি ব্যবহার করব এখানে আমরা পুনরাবৃত্তভাবে অ্যারেটিকে দুটি ভাগে ভাগ করব যদি শেষ উপাদানগুলি আলাদা হয়, যদি এর উভয় প্রান্তের উপাদান একই হয়, এর অর্থ অ্যারের সমস্ত উপাদান একই রকম যেমন অ্যারেটি ইতিমধ্যে সাজানো হয়েছে৷
উদাহরণ
#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
