查找给定数字组中的数字频率

假设我们在C++中有一个向量/数组,我们希望计算这N个元素中哪一个具有最大重复次数并输出最高计数.哪种算法最适合这项工作.

例:

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

输出为4,因为2次出现4次.这是2次发生的最大次数.

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

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

针对空间进行优化:

Quicksort(例如)然后遍历项目,仅跟踪最大计数.最好是O(N log N).

针对速度进行了优化:

迭代所有元素,跟踪单独的计数.该算法将始终为O(n).