Finding Mode of Vector of Ints in C++
bmcnett's approach works great if number of elements are small enough. If you have large number of elements but the all element value are with in a small range using map/hashmap works well. Something like
typedef std::pair<int, int> mode_pair;
struct mode_predicate
{
bool operator()(mode_pair const& lhs, mode_pair const& rhs)
{
return lhs.second < rhs.second;
}
};
int modeFunction()
{
std::map<int, int> mode_map;
for (int n = 0; n < 100; n++)
mode_map[numVector[n]]++;
mode_predicate mp;
return std::max_element(mode_map.begin(), mode_map.end(), mp)->first;
}
since all the values are between 0 and 100, you can find the mode efficiently with a histogram:
std::vector<int> histogram(101,0);
for( int i=0; i<100; ++i )
++histogram[ numVector[i] ];
return std::max_element( histogram.begin(), histogram.end() ) - histogram.begin();
Since mode is the number that occurs most frequent you shouldn't change numMode
unless the new number's count is greater than numMode
's count.
EDIT: To clarify, you need to keep a separate count for the current element and the current number that you think is the mode. Ideally, setting newMode
to the first element is a good approach.
In addition, mode isn't necessary unique (i.e. "1 1 2 2"). You may want to keep that in mind if you care about that.
newMode = element[0]
modeCount = # of occurrence of newMode
for ( i-th element from [1 to end] ) {
tmpCount = # of occurrence of element[i]
if tmpCount > modeCount {
newMode = element[i]
modeCount = tmpCount
}
}