Accueil › Coding & algorithmique › Les références communes, une seule fois chacune
Les références communes, une seule fois chacune
Exercice de la série « Maps, Sets et regroupements »debutant
Le problème. Deux inventaires. On veut les références présentes dans les deux, sans doublon, dans l'ordre où elles apparaissent dans le premier inventaire.
Écrivez communes(a, b).
| Appel | Résultat attendu |
|---|---|
communes([1, 2, 2, 3], [2, 3, 4]) |
[2, 3] |
communes([3, 1], [1, 3]) |
[3, 1] — l'ordre de a |
communes([1, 1], [1]) |
[1] |
communes([5, 6], [7]) |
[] |
communes([], [1]) |
[] |
Ce qu'on attend. O(n + m). Chercher chaque élément de a dans b
avec includes coûterait O(n × m).
Le piège. Deux exigences se cumulent : pas de doublon, et l'ordre du premier inventaire. Il faut donc deux ensembles, pas un.
Cas de test
[[1,2,2,3],[2,3,4]][[3,1],[1,3]][[1,1],[1]][[5,6],[7]][[],[1]][[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.