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.

Answer 2

If you are not allowed to use collection then you can try below code :

public int getPopularNumber(){
    int inputArr[] = {1, 2, 3, 4, 4, 5 ,4 ,5 ,5}; // given input array
    int[] tempArr = new int[inputArr.length];
    int[] maxValArr = new int[inputArr.length];

    // tempArr will have number as index and count as no of occurrence
    for( int i = 0 ; i < inputArr.length ; i++){
        tempArr[inputArr[i]]++;     
    }

    int maValue = 0;
    // find out max count of occurrence (in this case 3 for value 4 and 5) 
    for( int j = 0 ; j < tempArr.length ; j++){
        maValue = Math.max(maValue, tempArr[j]);        
    }

    int l =0;
    // maxValArr contains all value having maximum occurrence (in this case 4 and 5)
    for( int k = 0 ; k < tempArr.length ; k++){
        if(tempArr[k] == maValue){
            maxValArr[l] = k;
            l++;
        }       
    }

    return maxValArr[(int)(Math.random() * getArraySize(maxValArr))];

}

private int getArraySize(int[] arr) {
    int size = 0;
    for( int i =0; i < arr.length ; i++){
        if(arr[i] == 0){
            break;
        }
        size++;
    }
    return size;
}

Answer 3

that's hard as hell :D After some trying, I guess I have it (If there will be 2 numbers with same frequency, it will return first found):

    int mostPopNumber =0;
    int tmpLastCount =0;

    for (int i = 0; i < array.length-1; i++) {
        int tmpActual = array[i];
        int tmpCount=0;
        for (int j = 0; j < array.length; j++) {
            if(tmpActual == array[j]){
                 tmpCount++;
            }
        }
        // >= for the last one 
        if(tmpCount > tmpLastCount){
            tmpLastCount = tmpCount;
            mostPopNumber = tmpActual;
        }
    }

    return mostPopNumber;

--

Hah your code give me idea- you cant just remember last most popular number, btw I've found it solved there Find the most popular element in int[] array :)

EDIT- after many, and many years :D, that works well :) I've used 2D int and Integer array - you can also use just int array, but you will have to make more length array and copy actual values, Integer has default value null, so that's faster Enjoy

public static void main(String[] args) {
    //income array
    int[] array= {1,1,1,1,50,10,20,20,2,2,2,2,20,20};

    //associated unique numbers with frequency
    int[][] uniQFreqArr = getUniqValues(array);

    //print uniq numbers with it's frequency
    for (int i = 0; i < uniQFreqArr.length; i++) {
        System.out.println("Number: " + uniQFreqArr[i][0] + "  found : " + uniQFreqArr[i][1]);
    }

    //get just most frequency founded numbers
    int[][] maxFreqArray = getMaxFreqArray(uniQFreqArr);

    //print just most frequency founded numbers
    System.out.println("Most freq. values");
    for (int i = 0; i < maxFreqArray.length; i++) {
        System.out.println("Number: " + maxFreqArray[i][0] + "  found : " + maxFreqArray[i][1]);
    }

    //get some of found values and print
    int[] result = getRandomResult(maxFreqArray);
    System.out.println("Found most frequency number: " + result[0] + " with count: " + result[1]);
}

//get associated array with unique numbers and it's frequency
static int[][] getUniqValues(int[] inArray){
    //first time sort array
    Arrays.sort(inArray);

    //default value is null, not zero as in int (used bellow)
    Integer[][] uniqArr = new Integer[inArray.length][2];

    //counter and temp variable
    int currUniqNumbers=1;
    int actualNum = inArray[currUniqNumbers-1];

    uniqArr[currUniqNumbers-1][0]=currUniqNumbers;
    uniqArr[currUniqNumbers-1][1]=1;

    for (int i = 1; i < inArray.length; i++) {
        if(actualNum != inArray[i]){
            uniqArr[currUniqNumbers][0]=inArray[i];
            uniqArr[currUniqNumbers][1]=1;
            actualNum = inArray[i];
            currUniqNumbers++;
        }else{
            uniqArr[currUniqNumbers-1][1]++;
        }
    }

    //get correctly lengthed array
    int[][] ret = new int[currUniqNumbers][2];
    for (int i = 0; i < uniqArr.length; i++) {
        if(uniqArr[i][0] != null){
            ret[i][0] = uniqArr[i][0];
            ret[i][1] = uniqArr[i][1];
        }else{
            break;
        }
    }
    return ret;
}

//found and return most frequency numbers
static int[][] getMaxFreqArray(int[][] inArray){
    int maxFreq =0;
    int foundedMaxValues = 0;

    //filter- used sorted array, so you can decision about actual and next value from array
    for (int i = 0; i < inArray.length; i++) {
        if(inArray[i][1] > maxFreq){
            maxFreq = inArray[i][1];
            foundedMaxValues=1;
        }else if(inArray[i][1] == maxFreq){
            foundedMaxValues++;
        }
    }

    //and again copy to correctly lengthed array
    int[][] mostFreqArr = new int[foundedMaxValues][2];
    int inArr= 0;
    for (int i = 0; i < inArray.length; i++) {
        if(inArray[i][1] == maxFreq){
            mostFreqArr[inArr][0] = inArray[i][0];
            mostFreqArr[inArr][1] = inArray[i][1];
            inArr++;
        }
    }
    return mostFreqArr;
}

//generate number from interval and get result value and it's frequency
static int[] getRandomResult(int[][] inArray){
    int[]ret=new int[2];
    int random = new Random().nextInt(inArray.length);

    ret[0] = inArray[random][0];
    ret[1] = inArray[random][1];
    return ret;
}