使用哈希表來計算頻率 - 自制

Question

如果我允許額外存儲O（N），我可以使用哈希表和BST解決以下問題嗎？

1. 計算數組中所有元素的頻率？

2. 查找哪個數字在數組中重複最大次數？

我最關心的是整數元素。

Answer 1

是的，兩個任務都可以同時使用哈希表和BST，並且需要線性空間。

散列表和二叉搜索樹都可以實現映射接口，您可以在其中快速查找關鍵字並將其鏈接到值。

您可以使用此地圖界面來實現直方圖，該直方圖將從您的鍵映射到整數。
您迭代數組，併爲每個元素在地圖中查找它（作爲鍵）。如果該鍵存在，則獲取該值並將其增加1。
否則，插入這個新元素的地圖值1

當做到這一點，你有一個地圖滿足要求1.
爲了滿足第二個要求，只需重複地圖，找到相關的關鍵最高的價值，並返回它。

這是在需要線性額外空間的情況下完成的，並且在地圖基於散列表的情況下在O(n)中完成，而基於BST的O(nlogn)完成。 （對於BST，所有平均情況下，使用自平衡BST時間複雜度可以是O(nlogn)最差情況）。

C++ 11與哈希映射實現地圖界面

#include <iostream> 
#include <unordered_map> 
using namespace std; 

int main() { 
    int array[] = {1,9,9,7,5,4,1,2,0,1,0}; 
    std::unordered_map<int,int> histogram; 
    for (int x : array) { 
     auto in_map = histogram.find(x); 
     if (in_map == histogram.end()) { 
      histogram[x] = 1; 
     } else { 
      ++(in_map->second); 
     } 
    } 
    int most_occurances_element = -1; 
    int most_occurances = -1; 
    for (const auto& kv : histogram) { 
     if (kv.second > most_occurances) { 
     most_occurances_element = kv.first; 
     most_occurances = kv.second; 
     } 
    } 
    std::cout << "Most frequent element " << most_occurances_element << " with " 
     << most_occurances << " occurances."; 
    return 0; 
} 

注意，此答案是指整數（或其他類型的可枚舉）作爲元素的代碼。對於浮點而言，根據各種因素（「相等」的定義，元素的來源等等），答案可能完全不同。）