找出向量中出现最多的数字

Question

我有一些数字存储在矢量中.我想找到矢量中出现最多的数字.

有没有这样做的简单/快速算法(STL或其他)？

Answer 1

对它进行排序,然后迭代它并保留一个计数器,当前一个数字与前一个数字相同时,你会增加一个计数器,否则重置为0.还要跟踪到目前为止计数器的最高值是什么,以及达到该值时的当前数字.这个解决方案是O(n log n)(因为排序).

或者,您可以使用从int到int的散列映射(或者如果您知道数字在有限范围内,您可以只使用数组)并迭代向量,the_hashmap[current_number]每个数字增加1.然后遍历hashmap以找到其最大值(以及属于它的键).这需要一个hashmap数据结构(除非你可以使用也会更快的数组),这不是STL的一部分.

Answer 2

如果您想避免对 vector 进行排序v，请使用地图：

int max = 0;
int most_common = -1;
map<int,int> m;
for (vi = v.begin(); vi != v.end(); vi++) {
  m[*vi]++;
  if (m[*vi] > max) {
    max = m[*vi]; 
    most_common = *vi;
  }
}

这需要更多内存并且具有非常相似的预期运行时间。所需的内存应该是一个完整的向量副本，如果有很多重复的条目，则更少。