[Entrainement 2008] Problème Collection

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.

30 déc. 2017 à 11:51:48 Modifié le 1 jan. 2018 à 11:13:08

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.

Répondre au sujet

Vous devez vous enregistrer ou vous connecter pour poster des messages.