Tìm tần suất của mỗi phần tử trong một mảng phạm vi giới hạn trong thời gian ít hơn O (n) trong C ++

Giả sử chúng ta có một mảng các số nguyên. Mảng là A và kích thước là n. Nhiệm vụ của chúng ta là tìm tần suất của tất cả các phần tử trong mảng nhỏ hơn O (n) thời gian. Kích thước của các phần tử phải nhỏ hơn một giá trị M. Ở đây chúng ta sẽ sử dụng phương pháp tìm kiếm nhị phân. Ở đây, chúng ta sẽ chia một cách đệ quy mảng thành hai phần nếu các phần tử cuối khác nhau, nếu cả hai phần tử cuối của nó giống nhau, điều đó có nghĩa là tất cả các phần tử trong mảng đều giống như mảng đã được sắp xếp.

Ví dụ

#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);
}

Đầu ra

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