Determine the most common occurrence in an array

Question

Assume I have an array of doubles that looks like the following:

Array[10] = {10, 10, 10, 3, 10, 10, 6, 10, 10, 9, 10}

I need a function that can determine what the MAJORTY vote is in the array, in this case "10" because it is the number that appears the most often... And of course there is the situation when no majority exists (where they are equal), in that case I need to throw an exception...

Any clues? Aside from doing some really nasty looping on the array (for each index, determine how many exist with the same value, store a count in the array, and then scan the count array for the highest number and the value at that position is the winner, etc...)

Answer 1

Using a Map<Integer, Integer> should be simple as:

int mostFrequent(int... ary) {
    Map<Integer, Integer> m = new HashMap<Integer, Integer>();

    for (int a : ary) {
        Integer freq = m.get(a);
        m.put(a, (freq == null) ? 1 : freq + 1);
    }

    int max = -1;
    int mostFrequent = -1;

    for (Map.Entry<Integer, Integer> e : m.entrySet()) {
        if (e.getValue() > max) {
            mostFrequent = e.getKey();
            max = e.getValue();
        }
    }

    return mostFrequent;
}

Answer 2

Your first problem is that you have an "array of doubles", because equality is problematic with floating point data (identical numerical values can be represented by different bit patters, among other things). If your doubles are in fact (as in the example) integers, use int instead. Otherweise, think long and hard about how you define what values are equal for the purpose of representing the same vote.

As for determining the majority vote, use a Map with the "vote id" as key and the number of votes as value - then in the end iterate through the map to find the maximal value.