Most common values in an array

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 w开发者_JS百科ondering if there is a way that only one for/if loop(statement) could be used to find these values.

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.

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.

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");
        }

    }

}

    //find majority of a value in a array — O(n log n) -> wrost case O(n)
void findMajority(){
    //sort
    sort(begin(sarray),end(sarray));
    //sarray[0] is our first number already counted
    int cont=1;
    int leader = sarray[0];
    //temp variables to know when we changed to a different number
    int tempLeader=0;
    int tempCont=0;
    //loop through sarray.size()
    for(unsigned int i=1; i<size; i++){
        if(tempLeader!=sarray[i]) //if we changed number tempCont is 0
            tempCont=0;

        if(sarray[i]==leader){ //if the current number in the array is our leader then keep counting
            cont++;
        }
        else{ //if not, then our new number will be tempLeader and we count that one
            tempLeader=sarray[i];
            tempCont++;
            if(tempCont>cont){ //its not higher occurences than our last number? skip, else we got a new leader
                leader=tempLeader;
                cont=tempCont;
                tempLeader=0;
                tempCont=0;
            }
        }
    }
    cout << "leader is" << leader << endl;
}

sorry, its a crappy solution, but it works like you asked, hope it helps