Получение самого «популярного» номера из массива

Question

Мне нужно домашнее задание получить самое «популярное» число в массиве (число на самой высокой частоте), а если есть несколько номеров с одинаковым количеством показов, получите некоторое число случайным образом. После более трех часов безуспешных попыток, и либо поиска в Интернете, это то, что я получил:

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

Этот код работу, но не принимаю во внимание важные прецедентного, если есть больше чем один номер с тем же подсчетом. Тогда он просто получит первый. например: int[]a = {1, 2, 3, 4, 4, ,5 ,4 ,5 ,5}; Код будет захватывать 4, так как он показан первым, и это не случайно, как должно быть. Другое дело - поскольку это домашнее задание, я не могу использовать ArrayList/карты и прочее, которые мы до сих пор не изучали. Любая помощь будет оценена по достоинству.

Answer 1

Поскольку они не дали вам какой-либо временной границы сложности, вы можете «переборщить» проблему, сканируя массив N^2 раза. (отказ от ответственности, это самый интуитивный способ сделать это, а не самый быстрый или самый эффективный с точки зрения памяти и процессора).

Вот некоторые псевдо-код:

1. Создайте еще один массив того же размера, что и исходный массив, то это будет «массив появление»
2. Нулевые его элементы
3. Для каждого индекса i в исходном массиве, итерации исходного массива и приращения элемента в массиве вхождения на i каждый раз, когда сканирование находит дубликаты значения, хранящегося в i в исходном массиве.
4. Найти максимум в массиве возникновения
5. Возвращение значения, хранящегося в этом индексе в исходном массиве

Таким образом, вы имитировать использование карт с помощью всего другого массива.

Answer 2

Если вы не можете использовать коллекцию, то вы можете попробовать ниже код:

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

, что трудно, как ад: D После некоторых попыток, я предполагаю, что я его (если будет 2 номера с та же частота, она будет возвращать первый найдено):

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; 

-

Хах ваш код дает мне idea- вы не можете просто вспомнить последний самый популярный номер, кстати, я нашел, что решил там Find the most popular element in int[] array :)

Edit- после многих и многих лет: D, что хорошо работает :) я использовал 2D Int и Integer массив - вы также можете использовать только целочисленный массив, но вам придется сделать больше длины массива и скопировать фактические значения, Integer имеет значение по умолчанию NULL, так что быстрее Наслаждайтесь

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

Answer 4

ты разрешено использовать String manipulati вместо карт/списков?: D

int[] arr = new int[] { 10, 5, 2, 4, 9, 10, 4, 4, 8, 7, 10}; 
String highest = ""; // Collecting all highest numbers in a String 
int highestCount = 0; 
for (int a : arr) { 
    int count = 0; 
    for (int b : arr) { 
     if (b == a) 
      count++; // Getting the number of the current value 
    } 
    if (count > highestCount) { 
     highest = ":" + a + ":"; // new highest count found, overwriting before counted and collected values 
     highestCount = count; 
    } else 
    if (count == highestCount && !highest.contains(":" + a + ":")) { // if value is not in string yet. 
     highest += ":" + a + ":"; // values are wrapped in :x: to prevent ":xy:".contains("x") false positive 
    } 
} 
highest = highest.replaceAll("::", ":").replaceAll("^:", "") 
      .replaceAll(":$", ""); // remove first and last ":" and replace :: by : 
String[] highestNumbers = highest.split(":"); // split string by : 
highest = highest.replaceAll(":", ", "); // optional for output: replace : by , 
int randomOutput = Integer.parseInt(highestNumbers[(int) (Math.random() 
      * (highestNumbers.length - 1))]); // Get random number string and parse to Integer 
System.out.println("Highest count: " + highestCount + " for Number(s): " 
      + highest + " Random number: " + randomOutput); // output