Prépa Code Connexion Inscription

On appelle élément majoritaire d'une liste L un élément qui apparaît 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 apparaît 3 fois sur 4 (> 4//2 = 2), donc c'est l'élément majoritaire.

On demande une solution diviser pour régner, et non l'algorithme de vote de Boyer-Moore ni un simple comptage avec un dictionnaire.

Indice : si un élément est majoritaire dans lst, alors il est majoritaire dans au moins une des deux moitiés de lst (sinon il aurait au plus la moitié de chaque moitié, donc au plus la moitié du total). On coupe donc la liste en deux, on cherche récursivement un majoritaire dans chaque moitié, et on obtient au plus deux candidats. Il reste à compter les occurrences de chaque candidat dans la liste entière pour décider. Le cas de base est une liste à un seul élément.