在C ++中以小于O(n)的时间在有限范围的数组中查找每个元素的频率

假设我们有一个整数数组。数组为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