L'élément majoritaire, en deux passages

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 2 — Recherche séquentielle et dictionnaires

Énoncé

Un élément est majoritaire dans t s'il apparaît strictement plus de $n /2$ fois (où $n = len (t)$ ). Écrire une fonction majoritaire(t) qui renvoie cet élément s'il existe (ou None), en complexité $O (n)$ .

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 None

Le premier passage (comptage) prend $O (n)$ opérations. Le second passage (recherche de la clé vérifiant la condition) effectue au plus $n$ itérations. La complexité globale est $O (n)$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.