Determinare il caso più comune in un array

Question

Si supponga che ho una serie di doppie che è simile al seguente:

Array[10] = {10, 10, 10, 3, 10, 10, 6, 10, 10, 9, 10} 

Ho bisogno di una funzione in grado di determinare che cosa il voto majorty è nella matrice, in questo caso "10" perché è il numero che appare più spesso ... E ovviamente c'è la situazione in cui non esiste la maggioranza (dove sono uguali), in quel caso ho bisogno di lanciare un'eccezione ...

Eventuali indizi? Oltre a fare un po 'brutto loop sull'array (per ogni indice, determinare quanti ne esistono con lo stesso valore, memorizzare un conteggio nell'array, quindi scansionare l'array count per il numero più alto e il valore in quella posizione è il vincitore , ecc ...)

Answer 1

Utilizzando un Map<Integer, Integer> dovrebbe essere semplice come:

int mostFrequent(int... ary) { 
    Map<Integer, Integer> m = new HashMap<Integer, Integer>(); 

    for (int a : ary) { 
     Integer freq = m.get(a); 
     m.put(a, (freq == null) ? 1 : freq + 1); 
    } 

    int max = -1; 
    int mostFrequent = -1; 

    for (Map.Entry<Integer, Integer> e : m.entrySet()) { 
     if (e.getValue() > max) { 
      mostFrequent = e.getKey(); 
      max = e.getValue(); 
     } 
    } 

    return mostFrequent; 
} 

Answer 2

Il primo problema è che si dispone di una "matrice di doppi", perché l'uguaglianza è problematica con i dati in virgola mobile (valori numerici identici possono essere rappresentati da diversi bit tracker, tra le altre cose). Se i tuoi duplicati sono in effetti (come nell'esempio) numeri interi, usa invece int. Altrimenti, pensa a lungo e duramente a come definisci quali valori sono uguali allo scopo di rappresentare lo stesso voto.

Per determinare il voto a maggioranza, utilizzare uno "voto id" come chiave e il numero di voti come valore, quindi utilizzare lo Map, quindi alla fine iterare la mappa per trovare il valore massimo.

Answer 3

Ordinare prima la matrice con ordinamento rapido, quindi eseguire la scansione e contare per la maggioranza - O (n ln n). Se l'intervallo di elementi è noto in anticipo, ad esempio tra {1, k}, è possibile utilizzare un ordinamento di conteggio che verrà eseguito in O (n + k).

Come un leggero miglioramento, come si sta eseguendo la scansione della matrice ordinata, se si trova il valore che ha più di n/2 occorrenze che hai fatto.

Answer 4

Si potrebbe fare ciò: convertire la matrice in una lista e ordinarla. Scegli il primo indice e chiama lastIndexOf (obj) sul valore. Fatelo per ogni nuovo valore che incontrate, calcolate l'intervallo del valore e memorizzate i risultati dell'intervallo più grande in una variabile.

Answer 5

Con una serie di doppi questo potrebbe non essere facile poiché i confronti di uguaglianza sui doppi sono piuttosto problematici. Se si riesce a farla franca con l'utilizzo di numeri interi, si può fare qualcosa di simile al seguente:

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); 
    for(int element: Array) 
    { 
     Integer frequency = map.get(element); 
     map.put(element, (frequency != null) ? frequency + 1 : 1);  
    } 
    int mostFrequentItem = 0; 
    int[] maxFrequencies = new int[2]; 
    maxFrequencies[0]  = Integer.MIN_VALUE; 

    for(Entry<Integer, Integer> entry: map.entrySet()) 
    { 
     if(entry.getValue()>= maxFrequencies[0]) 
     { 
      mostFrequentItem = entry.getKey(); 
      maxFrequencies[1] = maxFrequencies[0]; 
      maxFrequencies[0] = entry.getValue(); 
     } 
    } 
    if(maxFrequencies[1] == maxFrequencies[0]) 
     throw new Exception();//insert whatever exception seems appropriate 
      return mostFrequentItem 

Ciò avrà O (n) le prestazioni, quindi dovrebbe essere abbastanza ottimale nel comportamento asintotico delle prestazioni. Se i tuoi doppi non sono i risultati dei calcoli ma provengono da un'altra fonte, cioè se puoi essere sicuro che i valori che sono fondamentalmente uguali saranno ugualmente rappresentati, potresti farla franca usando lo stesso metodo per i doppi, tuttavia vorrei consiglio comunque di fare attenzione che questo sia davvero il caso.

Edit: alcuni miglioramenti delle prestazioni come suggerito nel commento oltre a sostenere il controllo per caso ambiguo

Answer 6

Che cosa si vuole veramente fare è quello di contare le occorrenze di alcune voci insieme dato. Infatti, questo è stato precedentemente chiesto meno di un giorno fa, potresti voler esaminare questo very relevant question.

Answer 7

Come @Grizzly sottolinea, doppie sono problematici dal punto di vista computazionale.Suggerirei anche che non hanno senso dal punto di vista del dominio del problema; i doppi non hanno alcun senso con il voto a maggioranza!

Quindi supponiamo che 10 e 6 e così via siano identificatori di numeri interi per le cose per le quali le persone votano. Supponiamo inoltre che tu sappia che gli utenti possono votare qualsiasi valore da 0 a 10.

int[] votes = ... 
int[] voteCounts = new int[11]; // 11 could be calculated ... 
for (int vote : votes) { 
    voteCounts[vote]++; 
} 
int majority = (votes.length + 1)/2; 
for (int i = 0; i < voteCounts.length; i++) { 
    if (voteCounts[i] >= majority) { 
     return i; // the winner! 
    } 
} 
throw new NoClearMajorityException(...); 

Questo algoritmo è O(N) nel tempo e nello spazio O(M), dove M è il più grande identificatore. Il problema è che funziona solo (come scritto) se gli identificatori sono interi.

Answer 8

Ho appena creato una bella e piccola tale soluzione con il nuovo Java 8:

import java.util.Arrays; 
import java.util.Collection; 
import java.util.HashMap; 
import java.util.Map; 

public class MostCommonObject { 
    public static void main(String[] args) { 
     System.out.println(mostCommonObject(new Integer[] { -4, 1, -2, 3, 1, -2, 3, 1 })); 
    } 

    public static <T> T mostCommonObject(T[] array) { 
     return mostCommonObject(Arrays.asList(array)); 
    } 

    public static <T> T mostCommonObject(Collection<T> collection) { 
     Map<T, Integer> map = new HashMap<>(); 
     collection.forEach(t -> map.compute(t, (k, i) -> i == null ? 1 : i + 1)); 
     return map.entrySet().stream().max((e1, e2) -> Integer.compare(e1.getValue(), e2.getValue())).get().getKey(); 
    } 
} 

Answer 9

provare questo,

Integer[] array=new Integer[]{10, 10, 10, 3, 10, 10, 6, 10, 10, 9, 10}; 

    List<Integer> demoList=new ArrayList<Integer>(Arrays.asList(array)); 

    Set<Integer> set=new HashSet<Integer>(demoList); 

    Map<Integer,Integer> myMap=new HashMap<Integer, Integer>(); 

    for (Integer integer : set) 
    { 
     int count=Collections.frequency(demoList, integer); 
     myMap.put(count, integer);    
    } 

    int maxOccurance=myMap.get(Collections.max(myMap.keySet()));