Liste et occurrence

[MyJero]

Bonjour,
J'ai une liste d'entiers de taille n et je sais qu'il y a seulement k différents entiers dans cette liste. Je voudrais savoir lequel de ces entiers apparait le plus grand nombre de fois en utilisant le fait que k est nettement inférieur à n. En fait j'ai l'impression de presque avoir l'algorithme car je sais le faire si ces entiers vont de 0 à k mais pourtant ça coince...
L'unique critère qui m'intéresse ici est la vitesse d'exécution. Je pense que c'est faisable en O(n).
Merci d'avance pour votre précieuse aide !

[sabidi]

Je ne suis pas sûr de comprendre ta question, si j'ai bien compris, ton problème est le suivant:

- Tu as une liste de n nombres dont seulement k nombres différents
- Tu veux trouver le nombre qui se répète le plus dans cette liste
- k <<< n ça veut dire qu'on tend vers avoir un seul nombre qui se répète n fois dans cette liste

Un algorithme que je vois pour résoudre ce problème est de créer un tableau à deux dimensions de taille nx2, disons n colonnes et 2 lignes. La première ligne correspond aux nombres et la deuxième correspond aux nombres d’occurrences de chacun des nombres.

Parcourir ta liste et à chaque fois:
- Soit tu as un nouveau nombre que tu n'as jamais eu => tu remplis une nouvelle colonne de ton tableau avec les valeurs:
{nouveau nombre, 1}

- Soit tu as un nombre que t'as déjà eu => tu cherches la colonne de ton tableau et tu incrémentes le nombre de 1
{nombre déjà rencontré, nombre++}

Quand tu auras parcouru toute ta liste, il suffira de chercher le nombre d'occurrences le plus élevé dans ton tableau et prendre le nombre correspondant, c'est le nombre que tu cherches.

Par contre pour la complexité, je ne sais plus comment la calculer, il me semble bien que ça correspond à O(n) puisqu'on ne fait que parcourir simplement un tableau ou une liste de taille n sans récursivité.

[prgasp77]

Bonjour,

la complexité de l'algorithme proposé est un peu supérieur à O(n). En effet, cet algorithme est en deux parties : d'une part le parcourt de la liste d'entrée (les n nombres), et d'autre part le parcourt de la liste de travail (les k nombres). Dans la première étape, pour chaque élément de la liste d'entrée on doit rechercher un nombre dans la liste de travail ; pour chaque nouveau nombre rencontré on a de plus une insertion dans la liste de travail à faire. Dans la seconde étape, on parcourt la liste de travail.

Avec l'implémentation donnée par sabidi on a une complexité en O(nk + k + k) dans le cas moyen (bonne répartition des nombres de la liste d'entré).

On peut améliorer ceci en triant la liste de travail (tri par insertion, forcément). Cela nous donne, pour chaque élément de la liste d'entrée, une recherche par dichotomie dans la liste de travail et pour chaque nombre distinct de la liste d'entrée une insertion ; la recherche finale dans la liste de travail est elle inchangée. O(n.logk + k + k).

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Insertion du réel l(s)(0) dans la liste triée par ordre croissant l(0..n-1, 0..1)
Procédure insertion(l: liste de couples (réel, entier), s: entier)
Variables
   i: entier
   sample: réel
Début
   sample ← l(s-1)
   i ← s-1
   Tant Que i > 0 et l(i-1) > sample
      l(i) ← l(i-1)
      i ← i - 1
   Fin Tant Que
   l(i) ← sample
Fin Procédure.

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
// Recherche dichotomique de sample dans la liste de couples l, triée selon son membre de gauche
Fonction dichotomie(l: liste de couples (réel, entier), s: entier, sample: réel) : entier
Variables
   a, b, i: entiers
Début
   a <- 0
   b <- s-1
   Tant Que a <= b
      i <- (a+b)/2
      Si l(i)(0) = sample
         a <- b+1 // fin
      Sinon
         Si lmem(i)(0) < sample
            a <- i+1
         Sinon
            b <- i-1
         Fin Si
      Fin Si
   Fin Tant Que
   Si a <= b
      Retourner i
   Sinon
      Retourner s
   Fin Si
Fin Fonction.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Recherche l'entier de l le plus présent
Fonction element_le_plus_présent(l: liste de nombres, n : taille de l) : réel
Variables
   lmem: liste vide de couple (nombre, entier)
   smem: taille de lmem
   i: entier
Début
   smem ← 0
   Pour Chaque nombre sample de l
      i ← dichotomie(lmem, smem, sample)
      Si i < smem
         lmem(i)(1) ← lmem(i)(1)+1
      Sinon
         lmem(smem) ← (sample, 1)
         smem ← smem+1
         insertion(lmem, smem)
      Fin Si
   Fin Pour

   Retourner lmem(x)(0) tel que lmem(x)(1) soit maximal
Fin Procédure.

[disedorgue]

Bonjour,

On peut aussi gagner du temps, en mémorisant dans un couplet à part, lors de la création de la liste de travail, le nombre qui à le plus d'occurence.
Pour ce faire, il suffit juste de tester l'insertion en cours dans la liste de travail avec le fameux couplet et d'écraser celui-ci avec les valeur du couplet de la liste de travail si celui-ci à déjà un nombre supérieur d'occurence.

J'espère avoir été assez claire dans l'idée

Cordialement.

[prgasp77]

Cela revient sensiblement au même : pour maintenir ton couplet à jour, lors de chaque insertion tu as une opération à faire, soit k opérations au total ; et cette astuce ne te permet que d'économiser le parcours de la liste de k éléments en fin d'algo. On gagne k, mais on perd k.

Ce que tu proposes peut être intéressant, mais c'est au niveau de l'implémentation. Et cela n'est pas notre affaire ici.

Cdlt,

[davcha]

On peut aussi accélérer en ne parcourant pas les n entiers de ta liste, mais juste p entiers, p < n. Ce qui te donne une approximation, en supposant que la variance entre le nombre d'occurrence des différents nombres est suffisamment grand.