Java ( Comptage d'entiers distincts )

Question

Comment retourner le nombre de valeurs distinctes/uniques dans un tableau par exemple ?

int[] a = {1,2,2,4,5,5};

Answer 1

Set<Integer> s = new HashSet<Integer>();
for (int i : a) s.add(i);
int distinctCount = s.size();

Answer 2

Un ensemble stocke chaque élément unique (tel que défini par .equals()) une seule fois, et vous pouvez utiliser cela pour simplifier le problème. Créez un ensemble (j'utiliserais un HashSet), itérez votre tableau, en ajoutant chaque entier à l'ensemble, puis renvoyez .size() de l'ensemble.

Answer 3

Une méthode efficace : Trier le tableau avec Arrays.sort . Écrivez une boucle simple pour compter des valeurs égales adjacentes.

Answer 4

Cela dépend vraiment du nombre d'éléments dans le tableau. Si vous n'avez pas affaire à une grande quantité d'entiers, un HashSet ou un arbre binaire serait probablement la meilleure approche. D'un autre côté, si vous avez un grand tableau d'entiers divers (disons, plus d'un milliard), il pourrait être judicieux d'allouer un tableau de 2^32 / 2^8 = 512 MByte byte dans lequel chaque bit représente l'existence ou la non-existence d'un entier, puis de compter le nombre de bits définis à la fin.

Une approche par arbre binaire prendrait n * log n temps, tandis qu'une approche par tableau prendrait n temps. De plus, un arbre binaire nécessite deux pointeurs par nœud, ce qui augmente considérablement l'utilisation de la mémoire. Des considérations similaires s'appliquent également aux tables de hachage.

Bien sûr, si votre ensemble est petit, utilisez simplement le HashSet intégré.