Formations — 1 037 leçons en français

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, contains et remove. Adossé à une HashMap : les mêmes règles sur equals/hashCode s'appliquent.

Valeur de retour d'`add`

set.add(x) renvoie false si 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.

Lire l'explication détaillée et faire le quiz →

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.