Prépa Code Connexion Inscription

On appelle élément majoritaire d'une liste L un élément qui apparait strictement plus de len(L) // 2 fois dans L.

Écrire une fonction majoritaire(lst) qui prend une liste non vide d'entiers et : - renvoie l'élément majoritaire s'il en existe un, - renvoie None sinon.

Par exemple, dans [1, 2, 1, 1], l'élément 1 apparait 3 fois sur 4 (> 4//2 = 2), donc c'est l'élément majoritaire.

Indice : on peut utiliser l'algorithme de Boyer-Moore : parcourir la liste en maintenant un candidat et un compteur. Quand le compteur tombe a zéro, changer de candidat. A la fin, vérifier que le candidat est bien majoritaire.