資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟
心理
社會科學
時尚研究
法律研究在不到 O(n) 的時間內在 C++ 的有限範圍陣列中查詢每個元素的頻率
假設我們有一個整數陣列。陣列為 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
更新於：19-12-2019
243 次瀏覽
廣告