Accueil › Coding & algorithmique › Les Sets : unicité, intersection, appartenance
Les Sets : unicité, intersection, appartenance
Maps, Sets et regroupementsintermediaire
Un Set répond à une seule question — « cet élément est-il déjà là ? » — mais cette question est au cœur d'une quantité d'exercices.
Le motif « déjà vu » :
Set<Integer> vus = new HashSet<>();
for (int x : t)
if (!vus.add(x)) return x; // add renvoie false si déjà présent
Les opérations d'ensemble, directement disponibles :
Set<String> a = new HashSet<>(listeA);
Set<String> b = new HashSet<>(listeB);
Set<String> union = new HashSet<>(a); union.addAll(b);
Set<String> inter = new HashSet<>(a); inter.retainAll(b);
Set<String> diff = new HashSet<>(a); diff.removeAll(b);
Le bon Set selon le besoin :
| Besoin | Structure |
|---|---|
| Appartenance rapide | HashSet — O(1) |
| Ordre d'apparition conservé | LinkedHashSet |
| Ordre trié, recherche par proximité | TreeSet — O(log n) |
Et le piège qui coûte le plus cher : List.contains est en O(n). Dans une boucle, il crée un O(n²) que rien ne signale.
Les termes à connaître
- HashSet
Un ensemble sans doublon, en O(1) moyen pour
add,containsetremove. Adossé à uneHashMap: les mêmes règles surequals/hashCodes'appliquent.- Valeur de retour d'`add`
set.add(x)renvoiefalsesi l'élément était déjà présent. Tester ce booléen détecte un doublon sans second appel àcontains.- retainAll / removeAll
Intersection et différence d'ensembles, directement sur la collection :
a.retainAll(b)ne garde que le commun,a.removeAll(b)retire le commun.- LinkedHashSet
Un ensemble qui conserve l'ordre d'insertion. La réponse quand l'énoncé demande « sans doublon, dans l'ordre d'apparition ».
- TreeSet
Un ensemble trié, en O(log n). Offre
first,last,floor,ceiling,headSet,tailSet— précieux pour les recherches par proximité ou par intervalle.- Ensemble de vus
Le motif le plus courant : mémoriser les éléments déjà rencontrés pour détecter une répétition, un cycle, ou une position déjà visitée dans une grille.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.