Find which numbers are most represented in the vector

Question

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

Is there any simple / fast algorithm (STL or something else)?

Answer 1

Sort it, then swipe over it and save the counter, which you increase when the current number matches the previous number and reset to 0 otherwise. Also keep an eye on what was the highest counter value so far and what is the current number when that value was reached. This solution is O(n log n) (due to sorting).

Alternatively, you can use hashmap from int to int (or if you know the numbers are in a limited range, you can just use an array) and the_hashmap[current_number] over the vector, increasing the_hashmap[current_number] by 1 for each number. Then iterating through the hash map, you can find its greatest value (and its key). This requires a hashmap data structure, though (if you cannot use arrays, which will also be faster), that is not part of the STL.

Answer 2

If you want to avoid sorting your vector v , use a map:

 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; } } 

This requires more memory and has a very similar expected runtime. The required memory should be of the order of a full vector copy, less if there are many duplicate records.

Answer 3

Here is how I did it:

  int max=0,mostvalue=a[0]; for(i=0;i<a.size();i++) { co = (int)count(a.begin(), a.end(), a[i]); if(co > max) { max = co; mostvalue = a[i]; } } 

I just don’t know how fast this happens, i.e. O ()? If someone could calculate it and publish it here, that would be good.