Getting the most "popular" number from array

Question

I need for homework to get the most "popular" number in an array (the number in the highest frequency), and if there are several numbers with the same number of shows, get some number randomly. After more then three hours of trying, and either searching the web, this is what I got:

public int getPopularNumber(){
        int count = 1, tempCount;
        int popular = array[0];
        int temp = 0;
        for ( int i = 0; i < (array.length - 1); i++ ){
          if ( _buses[i] != null )
            temp = array[i]; 
            tempCount = 0;
            for ( int j = 1; j < _buses.length; j++ ){
              if ( array[j] != null && temp == array[j] ) 
                tempCount++;
            }           
            if ( tempCount > count ){
              popular = temp;
              count = tempCount;
            }
          }
          return popular;
}

This code work, but don't take into account an important case- if there is more than one number with the same count of shows. Then it just get the first one. for example: int[]a = {1, 2, 3, 4, 4, ,5 ,4 ,5 ,5}; The code will grab 4 since it shown first, and it's not random as it should be. Another thing- since it's homework I can't use ArrayList/maps and stuff that we still didn't learn. Any help would be appreciated.

Answer 1

Since they didn't give you any time complexity boundary, you can "brute force" the problem by scanning the the array N^2 times. (disclaimer, this is the most intuitive way of doing it, not the fastest or the most efficient in terms of memory and cpu).

Here is some psuedo-code:

1. Create another array with the same size as the original array, this will be the "occurrence array"
2. Zero its elements
3. For each index i in the original array, iterate the original array, and increment the element in the occurrence array at i each time the scan finds duplicates of the value stored in i in the original array.
4. Find the maximum in the occurrence array
5. Return the value stored in that index in the original array

This way you mimic the use of maps with just another array.