Most common values in an array

Question

How would I go about finding the three most common elements in an array? I am working with an array of length 10,000 with elements = random integer from 0-100.

I was thinking of using two arrays, one of length 100 and just incrementing by using an if statement. However, I was wondering if there is a way that only one for/if loop(statement) could be used to find these values.

Answer 1

You can do it in one loop, but I think you still need that second array.

I.e. loop over your input array, and each time you see a value, you increment the appropriate index in your 'counter' array. But, also keep 3 'top' indexes (sorted). Each time you increment, check your new value against the value at the top 3 indexes, accounting for the fact that you may be dealing with simply re-ordering your list of 'top' values.

Answer 2

If you are going to do this in a constant number of passes over the list, you need a second data structure.

If you have lower and upper bounds for the values in that set and the values are relatively dense, then an array of counters is a good solution.

Otherwise, it is better to use a Map<Integer, Integer>, where the keys are elements of the set and the values are counters.

Analysis

If you don't have lower / upper bounds on the set before you start, then you don't know big an array of counters to allocate. So you have to make a preliminary pass over the array to find the bounds ... and you now have a two pass solution.

If you do have lower and upper bounds but the set is sparse, then the cost of initializing the array of counts + the cost of finding the three largest counts will dominate the cost of counting the set elements. If the difference is large enough (i.e. the input is large & very sparse) a HashMap will be faster and will take less memory.

Alternatively

If you are allowed to change the array, you can sort it into ascending order O(NlogN) and then find the three most common elements in a single pass over the sorted array.

Answer 3

There are probably better ways to do this, but this is a way. I just printed the mode array, but you can sort it to see what number actually occurred the most. This is simple because we know the upper and lower bounds of the numbers we are messing with, but if you don't know those bounds then you need to take the advice Stephen C gave.

public class Main {

    public static void main(String[] args) {

        int i;
        int value;
        //one greater than max value because Math.random always returns a value less than 1.0
        //this number also works good for our mode array size
        int maxValue = 101;
        int[] originalArray = new int[10000];
        int[] modeArray = new int[maxValue];

        for(i = 0; i < originalArray.length; i++){
            value = (int) (Math.random() * maxValue);
            originalArray[i] = value;
        }


        for(i = 0; i < originalArray.length; i++){
            modeArray[originalArray[i]] += 1;
        }

        for(i = 0; i < modeArray.length; i++){
            System.out.println("Number " + i + " occurred " + modeArray[i] + " times");
        }

    }

}