C++ में O(n) समय से कम समय में सीमित श्रेणी के सरणी में प्रत्येक तत्व की आवृत्ति ज्ञात कीजिए

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है। सरणी A है, और आकार n है। हमारा कार्य ओ (एन) समय से कम समय में सरणी में सभी तत्वों की आवृत्ति का पता लगाना है। तत्वों का आकार एक मान से कम होना चाहिए जैसे कि एम। यहां हम द्विआधारी खोज दृष्टिकोण का उपयोग करेंगे। यहां हम सरणी को दो भागों में विभाजित करेंगे यदि अंतिम तत्व अलग हैं, यदि इसके दोनों अंतिम तत्व समान हैं, तो इसका मतलब है कि सरणी में सभी तत्व समान हैं क्योंकि सरणी पहले से ही क्रमबद्ध है।

उदाहरण

#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