Déterminer la fréquence la plus courante dans un tableau

Question

Supposons que j'ai un tableau de doubles qui ressemble à ce qui suit:

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

je besoin d'une fonction qui peut déterminer ce que le vote majorty est dans le tableau, dans ce cas "10" parce que c'est le numéro qui apparaît le plus souvent ... Et bien sûr il y a la situation où il n'y a pas de majorité (où ils sont égaux), dans ce cas je dois faire une exception ...

Des indices? En dehors de faire une boucle vraiment désagréable sur le tableau (pour chaque index, déterminez combien existent avec la même valeur, stockez un nombre dans le tableau, puis scannez le tableau de nombre pour le nombre le plus élevé et la valeur à cette position est le gagnant , etc ...)

Answer 1

L'utilisation d'un Map<Integer, Integer> doit être simple:

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

Votre premier problème est que vous avez un "tableau de doubles", car l'égalité est problématique avec les données à virgule flottante (les valeurs numériques identiques peuvent être représentées par différents modèles de bits, entre autres). Si vos doubles sont en fait (comme dans l'exemple) des entiers, utilisez plutôt int. Sinon, réfléchissez longuement et durement à la façon dont vous définissez quelles valeurs sont égales afin de représenter le même vote. Comme pour déterminer le vote majoritaire, utilisez un Map avec le "vote id" comme clé et le nombre de votes comme valeur - puis à la fin parcourez la carte pour trouver la valeur maximale.

Answer 3

Triez d'abord le tableau avec le tri rapide puis numérisez et comptez pour une majorité - O (n ln n). Si la plage d'éléments est connue à l'avance, disons entre {1, k}, alors un tri par comptage peut être utilisé et s'exécutera dans O (n + k). En guise de légère amélioration, lorsque vous analysez le tableau trié, si vous trouvez une valeur qui a plus de n/2 occurrences, vous avez terminé.

Answer 4

Vous pouvez faire ceci: Convertissez votre tableau en liste et triez-le. Choisissez le premier index et appelez lastIndexOf (obj) sur la valeur. Faites cela pour chaque nouvelle valeur que vous rencontrez, calculez la plage de la valeur et stockez les résultats de la plus grande plage dans une variable.

Answer 5

Avec un tableau de doubles cela peut ne pas être facile puisque les comparaisons d'égalité sur les doubles sont assez problématiques. Si vous pouvez sortir avec l'aide des entiers, vous pouvez faire quelque chose comme ce qui suit:

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 

Cela aura O (n) la performance, il devrait donc être assez optimale dans le comportement de la performance asymptotique. Si vos doubles ne sont pas le résultat de calculs mais proviennent d'une autre source, c'est-à-dire si vous pouvez être sûr que les valeurs qui sont fondamentalement les mêmes seront représentées également, vous pouvez utiliser la même méthode pour les doubles. recommande toujours d'être prudent que c'est vraiment le cas.

Edit: quelques améliorations de performance comme le suggère le commentaire ainsi que le soutien vérification des cas ambigus

Answer 6

Qu'est-ce que vous voulez vraiment faire est de compter les occurrences de certains éléments ensemble donné. En fait, cela a déjà été demandé il y a moins d'un jour, vous voudrez peut-être regarder dans ce very relevant question.

Answer 7

Comme le souligne @Grizzly sur, doubles sont problématiques du point de vue informatique.Je suggère également qu'ils n'ont pas de sens du point de vue de votre domaine de problème; les doubles n'ont aucun sens avec le vote majoritaire!

Supposons donc que 10 et 6 et ainsi de suite sont des identificateurs d'entiers pour les choses pour lesquelles les gens votent. Supposons également que vous savez que les utilisateurs peuvent voter n'importe quelle valeur de 0 à 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(...); 

Cet algorithme est O(N) dans le temps et dans l'espace O(M), où M est le plus grand identifiant. Le problème est que cela ne fonctionne (comme écrit) que si les identifiants sont des entiers.

Answer 8

Je viens de créer une si belle et petite solution avec la nouvelle 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

Essayez Celui-ci,

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())); 

tag