Как найти наиболее часто повторяющееся число в массиве?

Question

Я знаю, что есть похожие вопросы, подобные этому. Но вот трюк. Давайте предположим, что у нас есть этот массив:

int[] list = {1, 2, 3, 1, 0, 0, 0, 5, 6, 1569, 1, 2, 3, 2, 1569, 3}; 

System.out.println("Most repeated value is: " + ???);  

/* Now As you can see 0's, 1's, 2's and 3's has the same frequency "3 times". In this case, 
    I need to print the smallest number which is the most frequently repeated. So that, 
    prompt should be 0 */ 

Чтобы сделать его более понятным:

// All the digits except 5 and 6 and 1569's rest of the values repeated 3 times. I have to 
// print the smallest number which occurs most. 

Если вы могли бы показать мне код решения мудрого в Java я очень ценю это. Спасибо за проверку.

Answer 1

public static void main(String args[]) { 
    int[] list = {1, 2, 3, 1, 0, 0, 0, 5, 6, 1569, 1, 2, 3, 2, 1569, 3}; 

    Map<Integer,Integer> map = new HashMap<Integer,Integer>(); 
    for (Integer nextInt : list) { 
     Integer count = map.get(nextInt); 
     if (count == null) { 
      count = 1; 
     } else { 
      count = count + 1; 
     } 
     map.put(nextInt, count); 
    } 

    Integer mostRepeatedNumber = null; 
    Integer mostRepeatedCount = null; 
    Set<Integer>keys = map.keySet(); 
    for (Integer key : keys) { 
     Integer count = map.get(key); 
     if (mostRepeatedNumber == null) { 
      mostRepeatedNumber = key; 
      mostRepeatedCount = count; 
     } else if (count > mostRepeatedCount) { 
      mostRepeatedNumber = key; 
      mostRepeatedCount = count; 
     } else if (count == mostRepeatedCount && key < mostRepeatedNumber) { 
      mostRepeatedNumber = key; 
      mostRepeatedCount = count; 
     } 
    } 

    System.out.println("Most repeated value is: " + mostRepeatedNumber);  

} 

даст следующий вывод ...

Most repeated value is: 0 

Answer 2

Я думаю, мне не нужно упоминать алгоритм O (n^2).

В среднем О (п) Алгоритм:

int maxCount = 0; 
int maxKey = -1; 
foreach element in array 
{ 
    if(hashTable contains element) 
    { 
    increase the count; 
    if (count > maxCount) 
    { 
     maxCount = count; 
     maxKey = element 
    } 
    else if (count == maxCount && maxKey > element) 
    { 
     maxKey = element; 
    } 
    } 
    else 
    { 
    insert into hash Table with count 1; 
    if (1> maxCount) 
    { 
     maxCount = 1; 
     maxKey = element 
    } 
    } 
} 

О (п) + алгоритм к: же идея сделать массив с длиной = максимальное значение в массиве вместо Hashtable, и делать array[element]++;