Find which numbers appears most in a vector

Question

I have some numbers stored in a std::vector<int>. I want to find which number appears most in the vector.

e.g. in the vector

1 3 4 3 4 2 1 3 2 3

the element that occurs the most is 3.

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

Varden

See questions like: #1204813, #2184836 – Berkowitz

Answer 1

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).

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.

Hopeless

Just to add the obvious, for sorting using STL's sort: cplusplus.com/reference/algorithm/sort – Imminent

@Steve314: unordered_map will be in the upcoming standard. It is not in the 2003 (i.e. current) standard. – Hopeless

Wierd - I somehow got the idea that TR1 was the 2003 "first text revision". – Krantz

@Steve314: ISO 14882:2003 is effectively 14882:1998 plus TC1, TR1 is just a 'report' and not a corrigendum and hasn't yet made it into a new version of the standard. – Heterophyte

Ah - so somewhere along the line I confused TC1 with TR1 - that explains a thing or two. – Krantz

You don't need two passes. You can do this in a single pass, keeping track of the largest count "as you go". See code below. – Innovation

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 memory required should be on the order of a full vector copy, less if there are many duplicate entries.

Innovation

Answer 3

Try this

int FindMode(vector<int> value)
{ 
    int index = 0;
    int highest = 0;
    for (unsigned int a = 0; a < value.size(); a++)
    {
        int count = 1;
        int Position = value.at(a);
        for (unsigned int b = a + 1; b < value.size(); b++)
        {
            if (value.at(b) == Position)
            {
                count++;
            }
        }
        if (count >= index)
        {
            index = count;
            highest = Position;
        }
    }
    return highest;
}

Lardaceous

While this code may solve the question, including an explanation of how and why this solves the problem would really help to improve the quality of your post, and probably result in more up-votes. Remember that you are answering the question for readers in the future, not just the person asking now. Please edit your answer to add explanations and give an indication of what limitations and assumptions apply. – Bareback

time complexity increase to O(n^2) sometimes is too much – Envoi

Answer 4

This 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 it is, i.e. O() ? If someone could calculate it and post it here that would be fine.

Varden

It's O(n * n), so not the most efficient method but it is read-only and requires no additional storage if that's important. – Heterophyte

This is O(n^2), because every time you call count, it looks at every element in the vector. It can be done in O(n) (#513090) – Unaccomplished

Answer 5

Here is an O(n) generic solution for finding the most common element in an iterator range. You use it simply by doing:

int commonest = most_common(my_vector.begin(), my_vector.end());

The value type is extracted from the iterator using iterator_traits<>.

template<class InputIt, class T = typename std::iterator_traits<InputIt>::value_type>
T most_common(InputIt begin, InputIt end)
{
    std::map<T, int> counts;
    for (InputIt it = begin; it != end; ++it) {
        if (counts.find(*it) != counts.end()) {
            ++counts[*it];
        }
        else {
            counts[*it] = 1;
        }
    }
    return std::max_element(counts.begin(), counts.end(),
            [] (const std::pair<T, int>& pair1, const std::pair<T, int>& pair2) {
            return pair1.second < pair2.second;})->first;
}

Halfbound

This is O(nlogn) not O(n) -- std::map access is O(logn). It can be simplified by removing the if, but its still O(nlogn) – Teston

Answer 6

int findMostFrequentElement(const std::vector<int>& vec) {
    std::unordered_map<int, int> counts;
    for (const auto& elem : vec) {
        counts[elem]++;
    }

    auto maxCountElem = std::max_element(counts.begin(), counts.end(),
        [](const auto& a, const auto& b) {
            return a.second < b.second;
    });

    return maxCountElem->first;
}

Meow