[Entrainement 2008] Problème Collection

Bonjour, Je m'entrainais avec les annales des concours et j'ai réussi à résoudre ce problème : https://prologin.org/train/2008/semifinal/collection/139241#submit Cependant, le dernier test est validé après 60 sec. Je trouve cela très long et je me demandais donc s'il était possible de réduire ce temps avec un meilleur algorithme. Je précise que mon code était en Python.

Oui, il est largement possible de réduire ce temps. Ton algorithme doit certainement parcourir tout le tableau à chaque fois. Peut-être que tu devrais utiliser d'autres structures qui te permettent un accès plus direct à ce que tu cherches, comme par exemple un dictionnaire, ou collections.Counter.

Mon algorithme prend l'entier, l'ajoute à un tableau qui stocke la valeur des cartes déjà entrées, et compte le nombre de carte qui ont la même valeur que l'entier entré (avec liste.count(entier) ).
Finalement j'ai surdimensionné un tableau et incrémenté à la position de l'entier entré puis vérifié que la valeur à cette position ne dépassait pas 1. Sinon, cela voudrait dire qu'il a déjà été entré. Le temps maximum est passé à 0,11sec, ce qui est relativement plus court. Merci de ton aide.

Ce n'est quand même pas efficace, il n'y a pas de raison d'allouer un tableau gigantesque pour faire ça. Regarde du coté des dictionnaires, des sets et de collections.Counter, et essaie de comprendre pourquoi ces structures sont plus adaptées.

J'ai utilisé un dictionnaire, initialisé vide mais ma solution passe plus lentement (0.16 sec au dernier test) et prend plus de mémoire.

A chaque tour de boucle, j'essaie d'ajouter 1 à la valeur dont la clé est le numéro de carte entré. Si cela soulève une exception, cela veut dire que le numéro carte n'a pas encore été entré donc on ajoute ce numéro de même clé au dictionnaire.