Déterminer l'occurrence la plus courante dans un tableau

Supposons que j'ai un tableau de doubles qui se présente comme suit:

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

J'ai besoin d'une fonction qui permet de déterminer ce que le MAJORTY vote est dans le tableau, dans ce cas, "10", parce que c'est le nombre qui apparaît le plus souvent...
Et bien sûr il y a la situation où aucune majorité n'existe pas (où ils sont égaux), dans ce cas j'ai besoin de lancer une exception...

Des indices? À part de faire de très vilaines boucle sur le tableau (pour chaque indice, de déterminer combien existe avec la même valeur, de stocker un nombre dans le tableau, puis analyser le comte de tableau pour le plus grand nombre et de la valeur à cette position est le gagnant, etc...)

source d'informationauteur Shaitan00

algorithm java

À l'aide d'un Map<Integer, Integer> devrait ê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;
}

5

Votre premier problème, c'est que vous avez un "tableau de doubles", parce que l'égalité est problématique avec les données à virgule flottante (identique valeurs numériques peuvent être représentés par des bits différents modèles, parmi d'autres choses). Si votre double sont en fait (comme dans l'exemple des entiers, utilisez int à la place. Otherweise, penser à long et dur sur la façon de définir quelles sont les valeurs que sont l'égalité dans le but de représenter le même vote.

Que pour la détermination de la majorité des voix, utiliser un Map avec le "vote" id comme clé et le nombre de voix que la valeur - puis à la fin de l'itération à travers la carte pour trouver la valeur maximale.
4

Trier le tableau en premier w/tri rapide puis de les numériser et de les compter pour une majorité - O(n ln n). Si la gamme des éléments est connu à l'avance, entre par exemple {1,k}, puis à compter de tri peut être utilisé, qui va s'exécuter en O(n+k).

Comme une légère amélioration, que vous numérisez le tableau trié, si vous trouvez la valeur qui a plus que n/2 occurrences que vous êtes fait.

Avec un tableau de doubles, cela pourrait ne pas être facile, car l'égalité des comparaisons sur les doubles sont assez problématique.
Si vous pouvez vous en sortir avec l'aide de nombres 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

Ce sera O(n) les performances, il devrait être assez optimal de performance asymptotique de comportement. Si vos doubles ne sont pas les résultats des calculs, mais proviennent d'une autre source, c'est si vous pouvez être sûr que les valeurs qui sont au fond la même volonté d'être représentés de manière égale, que vous pourriez sortir avec l'aide de la même méthode pour les doubles, cependant, je voudrais encore vous recommandons d'être prudent que c'est vraiment le cas.

Edit: quelques améliorations de performances, comme suggéré dans les commentaires, ainsi que le soutien de la vérification pour les cas ambigus

2

@Grizzly points, un double problématique à partir d'un calcul de point de vue. Je dirais aussi qu'ils n'ont pas de sens du point de vue de votre problème de domaine; les doubles n'ont aucun sens du vote à la majorité!

Donc permet de supposer que 10 et 6 et ainsi de suite sont des entiers identificateurs pour les choses que les gens votent pour. Laisse aussi supposer 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 O(M) dans l'espace, où M est le plus grand de l'identificateur. Le hic, c'est qu'il fonctionne uniquement (comme l'écrit) si les identifiants sont des nombres entiers.

Je viens de créer une belle et petite solution avec le nouveau 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();
    }
}

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

0

Vous pourriez faire ceci: Convertir votre tableau à une liste et de les trier. Choisir le premier indice, et d'appeler lastIndexOf(obj) sur la valeur. Faites cela pour chaque nouvelle valeur que vous rencontrez, calculer la plage de la valeur et de stocker les résultats de la plus grande gamme dans une variable.
0

Ce que vous voulez vraiment faire est de compter les occurrences de certains éléments dans l'ensemble donné. En fait, c'était déjà demandé moins d'une journée il y a, vous voudrez peut-être regarder dans cette question très pertinente.

Vous devez vous connecter pour publier un commentaire.