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