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

Question

我有一些数字存储在 std::vector<int> 中。我想找出向量中出现最多的数字。

例如在向量中

1 3 4 3 4 2 1 3 2 3

出现最多的元素是 3 。

是否有任何算法（STL或其他）可以做到这一点？

原文由 VaioIsBorn 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

对它进行排序，然后遍历它并保留一个计数器，当当前数字与前一个数字相同时递增，否则重置为 0。还要跟踪到目前为止计数器的最高值是多少，以及达到该值时的当前数字是多少。这个解决方案是 O(n log n) （因为排序）。

或者，您可以使用从 int 到 int 的哈希图（或者如果您知道数字在有限范围内，您可以只使用数组）并遍历向量，将 the_hashmap[current_number] 每个数字增加 1。然后遍历 hashmap 以找到它的最大值（以及属于它的键）。不过，这需要一个 hashmap 数据结构（除非您可以使用更快的数组），这不是 STL 的一部分。

原文由 sepp2k 发布，翻译遵循 CC BY-SA 2.5 许可协议