Question
In C++ write a function named findMode that takes as parameters an array of int and the size of the array, and returns a vector containing the mode(s). If there is just a single most frequent value, the vector will only contain that one value, but if multiple values tie for maximum frequency, the vector will need to contain all such values. This includes the case where every number in the array appears only once. Each mode should appear only once in the vector. The values in the vector that is returned must be in ascending order. If you need to sort a vector, it's similar to sorting an array, but specifying the beginning and end of the vector look a little bit different. If your vector is named result, then it would look like this: "std::sort(result.begin(), result.end());".
The most straightforward approach is to:
Iterate (loop) through the array to find out what the highest frequency for any value is without worrying about storing any of the values.
Iterate through the array again, this time comparing the counts for each value to the highest frequency that you already found, if the count for a value is the same as the highest frequency, push that value into your results vector.
The file must be named: findMode.cpp
Explanation / Answer
#include #include #include #include // return the number of consecutive occurrences of the values starting at first std::size_t frequency_of( const int* first, const int* end ) { // pointer to the first element that is greater than the current value // http://en.cppreference.com/w/cpp/algorithm/upper_bound const int* next = std::upper_bound( first, end, *first ) ; return next - first ; } // return the the highest frequency for any value in [begin,end) // invariant: the sequence [begin,end) is sorted in ascending order std::size_t max_frequency( const int* begin, const int* end ) { assert( std::is_sorted(begin,end) ) ; // assert the invariant std::size_t max_so_far = 0 ; const int* curr = begin ; // start with the first value ; while( curr != end ) { const std::size_t frequency_of_this_value = frequency_of( curr, end ) ; max_so_far = std::max( max_so_far, frequency_of_this_value ) ; curr += frequency_of_this_value ; // repeat for the next value } return max_so_far ; } std::vector find_mode( int data[], std::size_t size ) { std::vector result ; int* begin = data ; // beginning of the sequence ; int* end = data + size ; // end of the sequence ; // 1. sort the values in ascending order std::sort( begin, end ) ; // 2. Iterate (loop) through the array to find out what the highest frequency // for any value is without worrying about storing any of the values. const std::size_t frequency_of_mode = max_frequency( begin, end ) ; // 3. Iterate through the array again, this time comparing the counts for each value // to the highest frequency that you already found, if the count for a value is // the same as the highest frequency, push that value into your results vector. const int* curr = begin ; // start with the first value ; while( curr != end ) { const std::size_t frequency_of_this_value = frequency_of( curr, end ) ; if( frequency_of_this_value == frequency_of_mode ) result.push_back(*curr) ; curr += frequency_of_this_value ; } return result ; } int main() { const std::size_t N = 20 ; int data[N] = { 8, 0, 7, 0, 5, 3, 1, 8, 7, 1, 5, 8, 3, 1, 7, 1, 5, 3, 7, 8 }; for( int v : find_mode( data, N ) ) std::cout