Compter nombre de répétitions des valeurs dans un tableau

Version imprimable

17/07/2011, 23h10
tabrouri2000

Compter nombre de répétitions des valeurs dans un tableau

bonjour
svp je cherche le code source en java pour compter nombre de répétition des valeurs dans un tableau.
par Exemple: l'utilisateur saisit la séquence de nombre suivantes:

12 14 15 12 22 30 12 22

Vous affichez:

12: 3 fois
14: 1 fois
15: 1 fois
22: 2 fois
30: 1 fois
17/07/2011, 23h33
Ivelios

Bonsoir,

Pourquoi ne le fait tu pas toi même?
ça te prendras moins de temps que de chercher le code tout fait.

je ai commencé mais je n'arrive pas a faire la partir de compter les valeur répéter malheureusement .
voila le code:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Scanner;
public class Tab{
 
	public static void main (String [] args){
     int valeur=0;
 
   	//déclaration du tableau
	int []valeurtab = new int[20];
 
		   // affichage du contenu
         System.out.println("affichge du tableau des valeur ayant une taille de :" +valeurtab.length );
 
          // création objet de type scanner
               Scanner scan = new Scanner(System.in);
 
      // demande de saisie les valeurs
         System.out.println("S.V.P 10 valeurs entre 0 et 30 :") ;
    for (int indice = 0 ; indice < valeurtab.length ; indice++){
                    valeur =scan.nextInt() ;
 
                                    // TESTER la valeur si entre 0 et 30
                                      while (valeur<0 || valeur >30 ){
	                                     //	String junk =scan.next();
	                                        System.out.print("S.V.P, Bien saisir une valeur entre 0 et 30: ");
	                                         valeur =scan.nextInt() ;
	                                       }
                        valeurtab[indice]=valeur;
 
System.out.println("valeur sure indice "+indice+" est: "+valeurtab[indice]);
 
}
 
 
 
}
 
}

Bonjour,

Si en plus il y a une contrainte entre 0 & 30 alors ce n'est pas compliqué :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 int[] tabResult = new int[31]; //Initialiser tabResult a 0 pour chaque case //Insere les valeurs de valeurtab vers tabResult for(int i=0;i<valeurtab.lenght;i++){ tabResult[valeurtab[i]] ++; } //Affichage for(int i =0;i<tabResult.lenght;i++){ System.out.println(i +" : "+ tabResult[i]+" fois "); }
Exemple :
valeurTab : 0,5,1,2,3,4,1,2,3,1,2,4
tabResult sera égal à : 1,3,3,2,2,1 -> un 0, 3 un, 3 deux,2 trois,2 quatre, 1cinq

Perso j'aurais utilisé une simple Map sans me préoccuper des perf :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public static void main(String[] args) { // Tableau à compter final int[] tab = { 12, 14, 15, 12, 22, 30, 12, 22 }; // Comptage Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (Integer item : tab) { Integer nombre = map.get(item); if (nombre == null) { nombre = 0; } nombre++; map.put(item, nombre); } // Affichage for (Integer key : map.keySet()) { Integer nombre = map.get(key); System.out.println("[" + key + "] --> " + nombre); } }
Ce qui donne :
Code:

1 2 3 4 5 6 [22] --> 2 [12] --> 3 [14] --> 1 [30] --> 1 [15] --> 1
Si tu veux que ça s'affiche ou que ça compte en même temps que ta saisie, tu peux même utiliser une Map<String, Integer> sur le même principe que ci-dessus. Par besoin d'avoir un tableau avec toutes les valeurs possibles, sauf si tu sais à l'avance que toutes les valeurs seront choisies.

Citation:

Envoyé par thierryler

Perso j'aurais utilisé une simple Map sans me préoccuper des perf :

Facile pour les perfs !

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
public static void main(String[] args) {
	// Tableau à compter
	final String[] tab = { "12", "14", "15", "12", "22", "30", "12", "22" };
 
	// Comptage
	Map<String, int[]> map = new HashMap<String, int[]>();
	for (String item : tab) {
		int[] nombre = map.get(item);
		if (nombre == null) {
			nombre = new int[] { 0 };
		        map.put(item, nombre);
		}
		nombre[0]++;
	}
 
	// Affichage
	for (String key : map.keySet()) {
		int[] nombre = map.get(key);
		System.out.println("[" + key + "] --> " + nombre[0]);
	}
}

La solution idéale sans utilisé de map, c'est de trier le tableau (ou la liste) des données saisies et de compter le nombre de valeurs identiques successives.
ex:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
public static void main(String[] args) {
	// Tableau à compter
	final String[] tab = { "12", "14", "15", "12", "22", "30", "12", "22" };
 
	// Comptage
        Arrays.sort(tab);
        String last=null;
        int count=0;
	for (String item : tab) {
		if (last == null) {
                	count=1;
                	last=tab;
                } else if (last.equals(tab)) {
                	count++;
                } else {
                        System.out.println("[" + last + "] --> " + count);
                        last=tab;
                        count=1;
                }
	}
	if (last != null) {
		System.out.println("[" + last + "] --> " + count);
        }
}

18/07/2011, 13h21
thierryler

Je ne suis pas certain qu'on y gagne à trier le tableau. Avec une map on ne parcourt qu'une seule fois la liste alors que si on tri... Si on a un million d'éléments...

thierryler / Nemek :
- Le problème du tri (que je sache), c'est que cela ne concerne que les tableaux 1D. Si le problème s'étend à 2D, la technique tombe à l'eau, alors que pour le parcours, il suffit de rajouter une boucle.
- Pourquoi utiliser un :

Code:

Map<String, int[]> map

et non pas un :

Code:

Map<String, int> map

tabrouri2000 :
- Le but de la création du tableau est-il UNIQUEMENT le dénombrement de tes valeurs ? (j'entends par là : utilises-tu les valeurs saisies ailleurs dans ton programme ?)

(après réflexion) Dans un cas comme dans l'autre, tu peux stocker le dénombrement directement à la saisie :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 import java.util.Scanner; public class Tab{ public static void main (String [] args){ int valeur=0; //déclaration des tableaux int []valeurtab = new int[20]; int []denombr = new int[31]; for(int i=0 ; i<31 ; i++){ denombr[i] = 0; } // affichage du contenu System.out.println("affichge du tableau des valeur ayant une taille de :" +valeurtab.length ); // création objet de type scanner Scanner scan = new Scanner(System.in); // demande de saisie les valeurs System.out.println("S.V.P 10 valeurs entre 0 et 30 :") ; for (int indice = 0 ; indice < valeurtab.length ; indice++){ valeur =scan.nextInt() ; // TESTER la valeur si entre 0 et 30 while (valeur<0 || valeur >30 ){ // String junk =scan.next(); System.out.print("S.V.P, Bien saisir une valeur entre 0 et 30: "); valeur =scan.nextInt() ; } valeurtab[indice]=valeur; denombr[valeur]++; System.out.println("valeur sure indice "+indice+" est: "+valeurtab[indice]); } } }

18/07/2011, 14h33
Logan Mauzaize
Citation:

Envoyé par thierryler

Je ne suis pas certain qu'on y gagne à trier le tableau. Avec une map on ne parcourt qu'une seule fois la liste alors que si on tri... Si on a un million d'éléments...
1. A condition de pouvoir stocker en mémoire 2 millions d'enregistrement :)
2. Avec le tri on parcourt autant de fois la liste qu'avec la Map.
La solution avec tri partait du principe qu'on ne puisse pas ou ne veuille pas utiliser la map.

Citation:

Envoyé par NeptuS

thierryler / Nemek :
- Le problème du tri (que je sache), c'est que cela ne concerne que les tableaux 1D. Si le problème s'étend à 2D, la technique tombe à l'eau, alors que pour le parcours, il suffit de rajouter une boucle.

Quel intérêt ?
De plus ca reste toujours possible :
- Soit en réécrivant un algorithme de tri (simple avec un algo de tri au choix pour chaque tableau définitif et le tri par fusion pour "rassembler" l'ensemble)
- Soit en créant une implémentation de liste qui est une vue de la structure multidimensionnelle.
Citation:

Envoyé par NeptuS

thierryler / Nemek :
- Pourquoi utiliser un :

Code:

Map<String, int[]> map

et non pas un :

Code:

Map<String, int> map

J'ose même pas répondre ...
Citation:
Envoyé par NeptuS

tabrouri2000 :

Code:

1 2 3 for(int i=0 ; i<31 ; i++){ denombr[i] = 0; }
C'est inutile
18/07/2011, 14h48
NeptuS

Pour la boucle ... disons que ça fait longtemps que je n'ai plus touché à Java
les int initialisés à 0, c'est ça ?

Pour la Map de tableaux d'int, je dirai qu'il faut un pointeur, c'est ça ?
Dans ce cas, j'aurai utilisé un Integer. Peut-être plus lourd qu'un int[1], mais comme on en a 30, ce n'est pas vraiment grave. (et plus propre, à mon goût)

Citation:

De plus ca reste toujours possible :
Soit en réécrivant un algorithme de tri (simple avec un algo de tri au choix pour chaque tableau définitif et le tri par fusion pour "rassembler" l'ensemble)
Soit en créant une implémentation de liste qui est une vue de la structure multidimensionnelle.

Pas sûr qu'il aie envie de monter une usine à gaz non plus. Le problème de base est assez simple.

Question subsidiaire pour Nemek : combien de temps met un utilisateur lambda pour saisir un million de nombres entre 0 et 30 ? :D

2 millions, ça passe nikel :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public static void main(String[] args) { // Tableau à compter // final int[] tab = { 12, 14, 15, 12, 22, 30, 12, 22 }; final int[] tab = new int[2000000]; final Random rand = new Random(); for (int i = 0; i < tab.length; i++) { tab[i] = rand.nextInt(31); } // Comptage final Map<Integer, int[]> map = new HashMap<Integer, int[]>(); for (Integer item : tab) { int[] nombres = map.get(item); if (nombres == null) { nombres = new int[] { 0 }; map.put(item, nombres); } nombres[0]++; } // Affichage for (Integer key : map.keySet()) { int[] nombres = map.get(key); System.out.println("[" + key + "] --> " + nombres[0]); } }
==> 64 ms pour 2 millions d'item
==> 608 ms pour 20 millions

Je vous épargne l'affichage du résultat ;-)

Bien vu le coup du int[] { 0 } ! Ca m'a pris quelques secondes aussi pour percuter...

Quand tu tries tes 2 millions d’éléments, ça va être "long". Et après il faut encore repasser dessus pour compter les occurrences à la suite. La map, ça fait juste un hash sur ta valeur donc ça va vite.

Bon en vrai je ne vous épargne rien lol :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 [0] --> 64349 [1] --> 64329 [2] --> 64878 [3] --> 64290 [4] --> 64902 [5] --> 64567 [6] --> 64480 [7] --> 65053 [8] --> 64431 [9] --> 64235 [10] --> 64458 [11] --> 64761 [12] --> 64186 [13] --> 64599 [14] --> 64322 [15] --> 64544 [17] --> 64788 [16] --> 64687 [19] --> 64125 [18] --> 64488 [21] --> 64614 [20] --> 64867 [23] --> 64129 [22] --> 64681 [25] --> 64151 [24] --> 64808 [27] --> 64517 [26] --> 64345 [29] --> 64017 [28] --> 64690 [30] --> 64709
Il y a bien, sans surprise 31 valeurs à peu près uniformément distribuées... Et en fait c'est hyper important car je n'aurais donc que 31 valeurs max dans ma map. Si je faisais l'autre solution, avec le tri, j'aurais précisément un tableau de 2 millions, qui plus est à trier...

Mais pour le coup, sur un grand tableau de départ, autant avoir cash un int[31] qu'on incrémente directement. A la limite, même si les valeurs du samedi et du dimanche sont toujours vides... Ca ne mange pas de pain
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public static void main(String[] args) { // Tableau à compter // final int[] tab = { 12, 14, 15, 12, 22, 30, 12, 22 }; final int[] tab = new int[2000000]; final Random rand = new Random(); for (int i = 0; i < tab.length; i++) { tab[i] = rand.nextInt(31); } // comptage final int[] result = new int[31]; for (Integer item : tab) { result[item]++; } // Affichage for(int i = 0; i< result.length;i++) { System.out.println("[" + i + "] --> " + result[i]); } }
==> 31 ms (2 millions)
==> 283 ms (20 millions)

Et heu, comment dire, pas de pointer en java.

18/07/2011, 19h23
usualSuspect

elle est bien bonne...
j'ai exactement le même exos pour un devoir et ramait au même endroit que tebrouri.
Merci à vous tous pour les explication - très utiles et efficaces :ccool:
18/07/2011, 20h04
thierryler

C'est pas tout d'avoir plusieurs solutions. Encore faut il savoir les expliquer ;-)
18/07/2011, 21h12
Ivelios

Citation:

autant avoir cash un int[31] qu'on incrémente directement

Mais c'est la solution que j'ai donné au début :aie::aie::aie:
18/07/2011, 21h20
thierryler

Oui et il nous a fallu une page de réponses pour arriver à la même conclusion dans ce cas particulier LOL
19/07/2011, 11h18
Logan Mauzaize

Citation:

Envoyé par NeptuS

Pour la boucle ... disons que ça fait longtemps que je n'ai plus touché à Java
les int initialisés à 0, c'est ça ?

Oui, c'était juste une piqure de rappel :)

Citation:

Envoyé par NeptuS

Pour la Map de tableaux d'int, je dirai qu'il faut un pointeur, c'est ça ?
Dans ce cas, j'aurai utilisé un Integer. Peut-être plus lourd qu'un int[1], mais comme on en a 30, ce n'est pas vraiment grave. (et plus propre, à mon goût)

Dans le monde Java, on dit une référence ou un objet.
Le problème de l'Integer c'est qu'il est immuable, potentiellement ca créé un objet à chaque tour de incrémentation.

Citation:

Envoyé par NeptuS

Pas sûr qu'il aie envie de monter une usine à gaz non plus. Le problème de base est assez simple.

Tu as complexifié le problème, la solution est donc un poile plus complexe.
Les solutions que j'ai envisagé sont du niveau d'un premier année de DUT.

Citation:

Envoyé par NeptuS

Question subsidiaire pour Nemek : combien de temps met un utilisateur lambda pour saisir un million de nombres entre 0 et 30 ? :D

Le temps d'écrire for (int i=0; i < 1000000; i++) :aie:
Sinon pour un million de 0 et 20 copier/coller (2^20 = ~1 000 000), je dirais 2 minutes. :mouarf:

Citation:

Envoyé par thierryler

2 millions, ça passe nikel

Parce que tu n'as pas 2 millions de valeurs possibles. J'avais pas vu que c'était limité à 30 valeurs possibles. :cry:

Citation:

Envoyé par thierryler

Je vous épargne l'affichage du résultat ;-)

T'aurais pu le faire au moins pour les 20 millions :mrgreen:

Citation:

Envoyé par thierryler

Quand tu tries tes 2 millions d’éléments, ça va être "long". Et après il faut encore repasser dessus pour compter les occurrences à la suite. La map, ça fait juste un hash sur ta valeur donc ça va vite.

La map doit tout de même rechercher la valeur dans la table de hashage. Comme tu as 30 valeurs possibles, ca va vite. Mais avec 2 millions d'éléments possibles, tu auras sûrement des "collisions" de hash et donc des valeurs en séquentiels. Chaque accès (recherche) dans la map te coutera de plus en plus.

Le mieux serait une TreeMap et des données récupérées au fil de l'eau.

Citation:

Envoyé par thierryler

Si je faisais l'autre solution, avec le tri, j'aurais précisément un tableau de 2 millions, qui plus est à trier...

Tu l'as déjà ton tableau de 2 millions. Ensuite tu peux le trier au fur et à mesure des ajouts.

Citation:

Envoyé par thierryler

Mais pour le coup, sur un grand tableau de départ, autant avoir cash un int[31] qu'on incrémente directement. A la limite, même si les valeurs du samedi et du dimanche sont toujours vides... Ca ne mange pas de pain

Effectivement s'il y a peu de valeur c'est la meilleure solution.

Count Numbers Occurrences

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
		int[] tab = new int[] { 1, 1, 7, 3, 2, 2, 2, 4, 1 };
		int[] count = new int[100];
		/*
		 * i : compteur, tmp : stocke temporairement la valeur à un certain index du
		 * tableau tab[]
		 */
		int i, tmp = 0;
		/*
		 * tmp agira comme une valeur d'index pour le tableau count et gardera une trace
		 * du nombre d'occurrences de chaque nombre
		 */
		for (i = 0; i < tab.length; i++) {
			tmp = tab[i];
			count[tmp]++;
		}
		for (i = 1; i < count.length; i++) {
			if (count[i] > 0 && count[i] == 1) {
				System.out.printf("%d se produit %d fois\n", i, count[i]);
			} else if (count[i] >= 2) {
				System.out.printf("%d se produit %d fois\n", i, count[i]);
			}
 
		}