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
[[1,2,3]][[1,3,1]][[]][[2,2]][[5]][[1,2,3,4,1]]
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.