使用 Hash Table 计算频率 - 自制

Question

如果允许额外存储 O(N)，我可以使用散列 table 和 BST 解决以下问题吗？

计算数组中所有元素出现的频率 ?
查找数组中哪个数字重复次数最多？

我最感兴趣的是整数元素。

Answer 1

是的，这两项任务都可以使用哈希 table 和 BST 来完成，需要线性 space。

散列table和二叉搜索树都可以实现map接口，可以通过key快速查找，link到value

您可以使用此映射接口实现直方图，将您的键映射到一个整数。
您迭代数组，并针对每个元素在映射中查找它（作为键）。如果此键存在，则获取值并将其加一。
否则，将这个新元素插入到值为 1 的地图中。

完成后，您就有了满足要求 1 的地图。
要满足第二个要求，只需迭代映射并找到与最高值关联的键，然后 return 它。

这是用需要的线性额外 space 完成的，当映射基于散列 table 时在 O(n) 中完成，当它基于散列 O(nlogn) 时完成在 BST 上。（所有平均情况下，对于 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;
}

请注意，此答案将整数（或其他可枚举类型）称为元素。对于浮点数，答案可能会因各种因素而完全不同（[=31= 的定义]、元素的来源...）

使用 Hash Table 计算频率 - 自制

Using Hash Table to count the frequencies - Self Made

arrays

algorithm

hashtable