Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Un doublon quelque part

Un doublon quelque part

Exercice de la série « Complexité, structures et cas limites »debutant

Le problème. Un formulaire a enregistré une liste d'identifiants. On veut savoir si l'un d'eux apparaît deux fois, sans supposer que la liste est triée.

Écrivez aUnDoublon(ids) qui renvoie true s'il existe au moins une valeur répétée, false sinon.

Appel Résultat attendu
aUnDoublon([1, 2, 3]) false
aUnDoublon([1, 3, 1]) true
aUnDoublon([]) false
aUnDoublon([2, 2]) true

Ce qu'on attend. Une double boucle répond juste en O(n²). Il existe une réponse en O(n), et c'est elle qu'on attend : pensez à ce qu'un ensemble vous fait gagner sur la question « ai-je déjà vu cette valeur ? ».

Cas de test

Écrire le code et le faire exécuter →

Votre code s'exécute réellement dans le navigateur, et la correction compare son résultat à celui d'une solution de référence.

La leçon qui prépare cet exercice

Les autres exercices de « Complexité, structures et cas limites »