Demi-Finale 2008 Collection : Arbre ou tableau ?

Bonjour,
J'ai une question concernant l'exercice "collection" de la demi-finale 2008.
J'ai 2 fois échoué au test n°5. La première fois à cause d'une limite de mémoire et la seconde à cause d'une limite de temps.

Lors du première essai j'avais créer un arbre, où je rangeais les nombres par ordre. Les plus petits à gauche et les autres à droites. Le temps de recherche était donc plus petit.
Malheuresement ça consommait trop de mémoire.

Le 2ème essai, à chaque nouveau nombre, je parcourais tout le tableau pour voir si je l'avais déjà rencontré.
Ici logique, ça prend trop de temps.

J'aimerai donc avoir quelques conseils :)
Merci d'avance.

Il y a une autre façon de faire avec un tableau, et qui permet de savoir si on a déjà rencontré un nombre, sans faire de recherche.

La solution est très simple, tu créés un tableau tab de taille valeur maximum + 1, et pour chaque carte contenue dans cartes, [...] est supérieur à 1, alors tu retournes la valeur (ou bien tu test avant si la valeur est supérieure à 0 ;))

Ah ! Merci. Je croyais que le tableau pouvait contenir des nombres supérieurs à la taille du tableau. Et si c'est le cas la solution que tu donnes est irréalisable \^\^

Tu n'as pas compris, je te parlais d'un tableau différent ;)

l'énoncé dit clairement :

Chaque entier sera compris entre 0 et 100000

donc tu créés un différent tableau de taille 100001 (de 0 à 100000), puis tu suis mon explication ;)

Ah ok merci ;)
Désolé.

Peut-être pas super top de donner la solution comme ça, ils l'auraient mise à côté de l'énoncé si c'était souhaitable, non ? Parce que bon, avec un peu de réflexion à comment résoudre le problème, on doit normalement arriver à envisager cette solution.

Oui, évitez de donner des solutions sur le forum SVP... Ca nuit à la recherche des autres :-)

En même temps, cette solution comporte un énorme inconvénient :
Si on a une liste de 5 éléments par exemple :
2, 3, 213, 1642, 213.
On doit allouer un tableau de mininum 1642+1 "cases". Et donc dans ce cas utiliser un arbre ou reparcourir le tableau edt beaucoup plus avantageux.
Mais dans cet exercice, en effet on peut utiliser cette solution \^\^

Gael, ici on dit bien que la taille du tableau et la borne sur les nombres sont les mêmes, donc la solution mentionnée plus haut ne gâche pas de mémoire et s'exécute en temps linéaire. Dans ce cas précis, ta solution est donc moins bonne :-) Je t'accorde qu'utiliser une table de hachage ou une structure d'ensemble est cependant le plus avantageux dans le cas général.