查找向量中出现次数最多的数字 [英] Find which numbers appears most in a vector

问题描述

我在矢量中存储了一些数字.我想找出向量中出现次数最多的数字.

I have some numbers stored in a vector . I want to find which number appears most in the vector.

是否有执行此操作的简单/快速算法(STL或其他)?

Is there any easy/fast algorithm (STL or whatever) that does this ?

推荐答案

对它进行排序，然后对其进行迭代，并保留一个计数器，当当前数字与先前的数字相同时，该计数器将递增，否则将其重置为0.还要跟踪到目前为止，计数器的最大值是多少，达到该值时当前的计数是多少.此解决方案是 O(n log n)(由于排序).

Sort it, then iterate through it and keep a counter that you increment when the current number is the same as the previous number and reset to 0 otherwise. Also keep track of what was the highest value of the counter thus far and what the current number was when that value was reached. This solution is O(n log n) (because of the sort).

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

Alternatively you can use a hashmap from int to int (or if you know the numbers are within a limited range, you could just use an array) and iterate over the vector, increasing the_hashmap[current_number] by 1 for each number. Afterwards iterate through the hashmap to find its largest value (and the key belonging to it). This requires a hashmap datastructure though (unless you can use arrays which will also be faster), which isn't part of STL.

这篇关于查找向量中出现次数最多的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！