Giả sử chúng ta có một mảng các số nguyên. Mảng là A, 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 trong thời gian nhỏ hơn O(n). Kích thước 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. Chúng ta sẽ chia đệ quy mảng thành hai phần nếu các phần tử ở hai đầu khác nhau, nếu cả hai phần tử đầu đều giống nhau, nghĩa là tất cả các phần tử trong mảng đều giống nhau vì 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); }
Kết quả
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