c++ - 查找给定数字组中数字的频率

Question

假设我们在 C++ 中有一个 vector/数组，我们希望计算这 N 个元素中哪些元素的重复出现次数最多，并输出最高次数。哪种算法最适合这项工作。

例子:

int a = { 2, 456, 34, 3456, 2, 435, 2, 456, 2}

输出为 4，因为 2 出现了 4 次。即 2 出现的最大次数。

Answer 1

对数组进行排序，然后快速传递以计算每个数字。该算法复杂度为O(N*logN)。

或者，创建一个哈希表，使用数字作为键。在哈希表中为您键入的每个元素存储一个计数器。您将能够一次计算所有元素；但是，算法的复杂性现在取决于您的 hasing 函数的复杂性。