Using double arrays to find the mode?

Question

I'm stuck on how to write a function that finds the mode or modes of a set of integers contained in an array, using that array and its length as parameters. I've found multiple solutions online on how to find the mode of an array, but I'm trying solve this problem in the following way:

Let's say the original array contains (0, 0, 1, 5, 5, 5, 7, 7, 7). I want to iterate through the array with a loop that finds the highest frequency of any amount without storing the mode, and store these frequencies in another array, where in this case, the new array would have the values (1, 2, 1, 1, 2, 3, 1, 2, 3). By finding the max value in the second array, I would find the highest frequency, being 3 in this case. Then I want to iterate through the original array again, comparing the highest frequency with the counts of each of the values in that array, and where there is a match, I return that value, which is 5 and 7 in this example I'm giving. Given the criteria here, how would you write this function for finding the mode or modes of a given array? (You can assume the array has already been presorted in ascending order).

Edit: Here's my preliminary code. I'm up to the step where I find the frequencies of each integer in the original array and store them into another array.

    void findMode(int array, int size){ 
        int count = 1;
        int freq[size];
        freq[0] = count;
        for (int pass = 1; pass < size; pass++){
            if (array[pass] == array[pass-1]){
            count++;
            freq[pass] = count;
            } 
          else{
              count = 1;
              freq[pass] = count;
              }
      }

`std::sort(array.begin(),array.end());` them first, then iterate. — Trevor Hickey, Feb 22 '17 at 16:31
How about using a map with the key as the integer and value as its occurence. Every time you see the same key again, increment the value. Though I am not sure how you would determine the max from that unless you iterate over the whole thing. EDIT: This question here shows the same thing http://stackoverflow.com/a/9370990/1083027 just keep a running count of max — Rahul Kadukar, Feb 22 '17 at 16:36
Wait, why would you want this? Why not just keep a list of the values that are equal to the highest number in the list, and wipe it if you find one higher then the max? — Fantastic Mr Fox, Feb 22 '17 at 16:42

score 0 · Answer 1 · answered Feb 22 '17 at 16:44

If you don't mind some extra storage (potentially O(N) storage) you could use a std::map to get the counts and then a linear search for the most frequent number.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <map>
#include <vector>

template<class InputIterator>
auto mode(InputIterator first, InputIterator last)
{
    using key_type = typename std::iterator_traits<InputIterator>::value_type;
    std::map<key_type, std::size_t> counts;
    for (auto it = first; it != last; ++it) {
        counts[*it]++;    
    }    
    return *std::max_element(counts.cbegin(), counts.cend(), [](auto const& lhs, auto const& rhs) {
        return lhs.second < rhs.second;
    }); // return mode + frequency
}

int main() {   
    auto v = std::vector<int> { 0, 0, 1, 5, 5, 5, 7, 7, 7 };   
    auto m = mode(v.cbegin(), v.cend());
    std::cout << m.first << ": " << m.second;
}

Live Example // prints 5: 3

Using double arrays to find the mode?

1 Answers1