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
Vous devez vous connecter pour publier un commentaire.
À l'aide d'un
Map<Integer, Integer>
devrait être simple: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.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:
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
@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
et6
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 de0
à10
.Cet algorithme est
O(N)
dans le temps etO(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:
Essayer celui-ci,
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.
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.