Eliminer les doublons dans un tableau d'entiers

**engi** · 17/03/2006, 09h45

bonjour,

tout est dans le titre !
je programme en C mais le principe est certainement identique quel que soit le langage.

bref, j'ai un tableau qui contient des entiers qui sont potentiellement répétés.
je voudrais retirer tous les doublons de ce tableau.

merci pour votre aide

**fearyourself** · 17/03/2006, 09h49

Envoyé par engi

bonjour,

tout est dans le titre !
je programme en C mais le principe est certainement identique quel que soit le langage.

bref, j'ai un tableau qui contient des entiers qui sont potentiellement répétés.
je voudrais retirer tous les doublons de ce tableau.

merci pour votre aide

Il y a un forum d'algorithmique... Vu que tu le remarques toi même:

je programme en C mais le principe est certainement identique quel que soit le langage.

Il serait bon d'aller là-bas pour poser cette question,
Jc

**PRomu@ld** · 17/03/2006, 21h05

bref, j'ai un tableau qui contient des entiers qui sont potentiellement répétés.
je voudrais retirer tous les doublons de ce tableau.

Plusieurs solution, méthode bête et méchante, tu fais la brute :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
Ti : tableau initial
Tf : tableau sans doublons
k : nombre d'entier sans doublons
 
Tf[1] = Ti[1];
 
pour i allant de 2 à N faire
 
     -- On regarde si on a pas déjà ajouté l'entier
     pour j allant de 1 à k faire
          si Ti[i] == Tf[j] alors
               passer au i suivant
          fin si
     fin pour
 
     -- Si on est ici alors c'est que ce n'est pas un doublon
     Tf[k] := Ti[i]
     k <- k + 1
fin pour

Bon c'est une méthode comme une autre, d'autres solutions existent et sont plus efficaces.

Une par exemple consiste à trier le tableau puis éliminer les doublons, en général, on appelle ça une élimination de plateau

Une autre solution consiste à vérifier lorsque tu ajoutes dans ton tableau que tu n'a pas de doublons avant d'insérer (ce n'est pas toujours possible), pour optimiser cette méthode, il faut que ton tableau soit trié.

Bref pleins de solutions possibles, reste à toi de voir celle qui te semble adaptable à ce que tu veux faire.

**Graffito** · 18/03/2006, 09h52

Bonjour,

Au cas ou la plage [min,max] soit suffisament petite disons de l'ordre de quelques centaines de milliers, on peut créer une chaine bits (Max-min+1 bits) qui indiquera si on a déjà la valeur dans le tableau.
Si oui, on mets le bit à 1
Sinon, on enlève la valeur.

**engi** · 18/03/2006, 09h58

merci pour ces infos.
je vais pouvoir mettre en application

**PRomu@ld** · 18/03/2006, 10h16

Envoyé par Graffito

Bonjour,

Au cas ou la plage [min,max] soit suffisament petite disons de l'ordre de quelques centaines de milliers, on peut créer une chaine bits (Max-min+1 bits) qui indiquera si on a déjà la valeur dans le tableau.
Si oui, on mets le bit à 1
Sinon, on enlève la valeur.

En fait, en prenant un tout petit peu de recul, il s'agit en fait d'une méthode de tri postal un peu modifiée (au lieu d'insérer, on regarde juste si on a déjà inséré)

**ToTo13** · 19/03/2006, 09h14

Bonjour,

si l'ordre des éléments n'est pas important, tu peux peux etre trier le tableau, comme ca tout les doublons seront cote à cote. De plus, si tu dois ajouter des éléments dans ton tableau, tu n'aura pas forcément besoin de le parcourir entièrement pour savoir si le numéro existe.

**Jedai** · 19/03/2006, 12h40

Si l'ordre n'est pas important et que tu risques d'avoir à insérer de nouveaux éléments, je te conseille de passer directement à un arbre rouge-noir, c'est l'une des meilleures structures pour ce type de problème.

--
Jedaï

**engi** · 19/03/2006, 13h15

arbre rouge-noir !

tu peux m'éclairer sur le sujet; jamais entendu parler

**PRomu@ld** · 19/03/2006, 13h35

Si l'ordre n'est pas important et que tu risques d'avoir à insérer de nouveaux éléments, je te conseille de passer directement à un arbre rouge-noir, c'est l'une des meilleures structures pour ce type de problème.

C'est peut être un peu radical, un simple tableau ou un arbre binaire de recherche simple (pas forcément rouge-noir ou autre ...) peut éventuellement être utilisé.

arbre rouge-noir !

tu peux m'éclairer sur le sujet; jamais entendu parler

Un arbre rouge noir est un arbre binaire de recherche équilibré dont les noeuds ont une couleur (rouge ou noire) pour aider à l'équilibre du noeud.

Un arbre binaire de recherche est un arbre qui est ordonné de la façon suivante :

les noeuds du sous arbre gauche sont plus petits que le noeud courrant. Les noeuds du sous arbre droit sont plus grand que le noeud courrant.

Un arbre rouge noir est un arbre équilibré ce qui signifie que les feuilles sont au même niveau (ou avec un décalage entre les niveaux d'au maximum un)

Je ne pense pas que tu en ai besoin.

**PRomu@ld** · 19/03/2006, 16h46

Même si ça n'est pas très complet (loin de là), tu peux ne serait ce que voir ce qu'est un arbre binaire de recherche ici :

http://rperrot.developpez.com/articl...arbres/#LVII-B

**engi** · 19/03/2006, 16h49

merci pour le lien

**PRomu@ld** · 19/03/2006, 17h18

Envoyé par engi

merci pour le lien

Oui, c'est une façon de se faire de la publicité gratuite !

**gangsoleil** · 20/03/2006, 10h43

Bonjour,

Dans ce cas précis, pourquoi ne pas faire la chose suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TabI : tableau initial (avec doublon(s))
TabF : tableau final (sans doublon)
 
Tri de TabI (quicksort par exemple si on veut un tri rapide)
 
tabF[0] = TabI[0];
j=1;
 
Pour i allant de 1 à fin_TabI -1
  Si  ( tabI[i] != tabI[i-1] )
   {
     TabF[j] = tabI[i];
     j++;
   }
   FSi
Fpour

Je pense qu'on obtient quelque chose d'assez rapide.

**Betatesteur** · 21/03/2006, 09h15

je préfère celle ci.

**pcaboche** · 21/03/2006, 12h32

Tu as indiqué que tu programmais en C. Si cela ne te gène pas d'inclure un peu de C++, tu peux utiliser un objet de type set disponible dans la STL. Sauf erreur, le type set est implémenté avec une structure d'arbre binaire de recherche (ça évite de réinventer la roue).

- Si l'ordre n'a pas d'importance, tu fais des insert dans ton set et à la fin, tu parcours le set avec un itérateur pour restituer le tableau sans doublon.

- Si l'ordre a l'importance, tu peux utiliser un set pour garder en mémoire les éléments déjà présents dans le tableau initial.

Voici un exemple d'utilisation de set (pour tester si un élément a déjà été rencontré) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <set>
using namespace std ;
 
...
 
set<int> ensemble ;
 
ensemble.insert(5) ;
ensemble.insert(14) ;
ensemble.insert(2) ;
...
if( ensemble.find(50) != ensemble.end() ) {
  // l'ensemble contient 50
} else {
  // l'ensemble ne contient pas 50
}

***
Si tu dois utiliser du C uniquement (pas de C++), la méthode "brute" suffit (pas besoin de quicksort). Il est d'ailleurs très simple de l'implémenter au moyen de pointeurs. Ici, la version "sur place" (non testée):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
// Retourne la nouvelle taille du tableau
 
int suppressionDoublons(int * tab, int taille) {
  int * p1, p2, p3, pFin ;
 
  p1 = tab ;
  pFin = tab + taille ;
 
  while (p1 < pFin) {
    p2 = p1+1 ;
    p3 = p2 ;
 
    while(p3 < pFin) {
 
      if (*p3 != *p1 ) {
         *p2 = *p3 ;
         p2++ ;
      }
       p3++ ;
 
    }
    pFin = p2 ;
    p1++ ;
  }
 
  return pFin - p1 ;
 
}

***
Note: Désolé d'avoir mis du code C/C++ au millieu d'un forum "algorithmes", mais c'est pour répondre à engi.

**engi** · 21/03/2006, 13h35

j'avais entendu dire que la stl pouvait me faciliter la tache.
ça à l'air de se confirmer.
as-tu le lien d'un site du style "La STL pour les nuls"

.
je programme en C et/ou C++, mais je n'ai jamais abordé tout ce qui touche de près ou de loin à la STL.
en tous les cas, merci pour ta réponse.

**Betatesteur** · 21/03/2006, 13h55

l'ami fidèle

**pcaboche** · 21/03/2006, 13h59

Envoyé par engi

j'avais entendu dire que la stl pouvait me faciliter la tache.
ça à l'air de se confirmer.

Oh que oui !

Déjà, tu as tous les conteneurs standards tels que les list, queue, deque, map, set...

Ensuite, tu as l'utilisation des "templates" qui te permet de définir des objets et des fonctions adaptables au type de données souhaité (ex: dans l'exemple précédent, on a utilisé un set d'entiers, mais on aurait pu aussi bien créer un set du type que tu veux)

Rien que ça, ça aide énormément !

Envoyé par engi

as-tu le lien d'un site du style "La STL pour les nuls"

.

Tout d'abord, je peux te conseiller le livre de Bjarne Stroustrup (l'inventeur du C++): "le langage C++". Une référence (le mien est complètement usé à force de le consulter!). Tu trouveras de nombreux livres presque aussi chers, mais beaucoup moins bons (et surtout moins complets)

Sinon, pour faire du chauvinisme communautaire, on a le "méga cours de C/C++" sur DVP. Tu t'intéresseras plus particulièrement à la partie II. La bibliothèque standard C++, notamment au Chapitre 17. Les conteneurs dans son ensemble.

Volià, tu sais tout. Bon C++ !

Envoyé par engi

en tous les cas, merci pour ta réponse.

De rien !

Eliminer les doublons dans un tableau d'entiers

Algorithmes et structures de données

Discussions similaires

Partager

Partager