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 utilisera l'algorithme de vote de Boyer-Moore, en un seul parcours de la liste : on maintient un candidat et un compteur ; si le compteur est à zéro, l'élément courant devient le candidat ; sinon on incrémente le compteur si l'élément courant est le candidat, et on le décrémente sinon. À la fin, vérifier par un second parcours que le candidat est bien majoritaire (sans ce contrôle, l'algorithme renvoie un candidat même quand il n'y a pas de majoritaire).