informatique (tronc commun des prépas scientifiques) · Chapitre 2 · Exercice de TD
L'élément majoritaire, en deux passages
Recherche séquentielle et dictionnaires · niveau 2
Énoncé
Un élément est majoritaire dans t s'il apparaît strictement plus de fois (où ). Écrire une fonction majoritaire(t) qui renvoie cet élément s'il existe (ou None), en complexité .
Corrigé
def majoritaire(t: list):
c = {}
for x in t:
c[x] = c.get(x, 0) + 1
seuil = len(t) / 2
for v in c:
if c[v] > seuil:
return v
return NoneLe premier passage (comptage) prend opérations. Le second passage (recherche de la clé vérifiant la condition) effectue au plus itérations. La complexité globale est .