Majority Element

+10

Vous recevez un tableau d’entiers nums de longueur n. Une valeur y apparaît plus de n / 2 fois : c’est l’élément majoritaire. Renvoyez cette valeur. Une valeur qui apparaît dans plus de la moitié du tableau est toujours unique, donc il existe exactement une réponse.

Fonction

majorityElement(nums: integer-array) → integer

numsinteger-array: le tableau d’entiers, dont une valeur occupe plus de la moitié
Renvoieinteger: la valeur qui apparaît plus de n / 2 fois

Contraintes

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Une valeur apparaît plus de nums.length / 2 fois.

Exemples

Entrée: nums = [3, 9, 3, 3, 4]
Sortie: 3
Explication: 3 apparaît trois fois parmi cinq éléments. Trois est supérieur à 5 / 2 = 2.5, et 9 et 4 apparaissent chacun une fois.

+15 tests cachés à la soumission

Pour aller plus loin

Peux-tu trouver l’élément majoritaire en O(n) avec O(1) mémoire supplémentaire, sans trier le tableau ?

Solution

Compter combien de fois chaque valeur apparaît répond à la question, mais ces comptages nécessitent une table de hachage. Pour s’en passer, il faut voir ce qui rend la majorité spéciale : elle est plus nombreuse que toutes les autres valeurs réunies. Associez chaque occurrence de cette valeur à une valeur différente et rayez-les toutes les deux ; il en restera toujours des occurrences. Le vote de Boyer-Moore effectue ces associations en un seul parcours, avec un candidat et un compteur.

Compter avec une table de hachage

Intuition

Parcours le tableau et conserve une table de hachage associant chaque valeur au nombre de fois où tu l’as vue. Après avoir augmenté de un le compte d’une valeur, vérifie si ce compte dépasse maintenant la moitié de la longueur du tableau. La première valeur à franchir ce seuil est la valeur majoritaire ; tu peux donc la renvoyer immédiatement.

Pour [3, 9, 3, 3, 4], le compte de 3 passe à 1 à l’index 0, à 2 à l’index 2 et à 3 à l’index 3. Trois occurrences sur cinq, c’est plus que 2,5 ; tu renvoies donc 3 sans lire le dernier élément.

La recherche et la mise à jour dans une table de hachage prennent O(1) en moyenne ; le temps d’exécution est donc O(n). La table peut contenir jusqu’à environ n / 2 valeurs différentes, donc la mémoire supplémentaire est O(n). L’approche suivante se passe de la table.

Algorithme

Crée une map vide associant chaque valeur à son compte.
Pour chaque élément x, ajoute 1 au compte de x.
Si ce compte multiplié par 2 est supérieur à la longueur du tableau, retourne x.

def majorityElement(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] * 2 > len(nums):
            return x

Vote de Boyer-Moore

Intuition

Considère le tableau comme une élection. Garde un candidate et un count de ses votes que rien n’a encore annulés. Un élément égal au candidat ajoute un vote. Un élément différent annule un vote, et les deux quittent la course ensemble. Lorsque le compteur est à 0, l’élément suivant devient le nouveau candidat.

Pourquoi la valeur restante à la fin est-elle la majorité ? Chaque annulation supprime deux valeurs différentes, donc elle supprime au plus une occurrence de la majorité. Disons que la majorité apparaît m fois. Il n’y a que n - m autres éléments, soit moins de m, donc ils ne peuvent pas annuler toutes ses occurrences. Tous les votes encore présents à la fin appartiennent au candidat final, et l’une des occurrences de la majorité en fait partie : le candidat est donc la majorité.

Avec [8, 8, 1, 1, 8, 1, 8], le compteur passe par 1, 2, 1, 0 : les deux 1 ont annulé les deux 8. Le 8 suivant recommence avec un compteur de 1, le 1 suivant l’annule, et le dernier 8 redevient le candidat. Tu renvoies 8. Un seul parcours avec deux variables donne un temps O(n) et une mémoire O(1).

Algorithme

Définissez candidate comme premier élément et count à 0.
Pour chaque élément x, si count vaut 0, faites de x le candidat.
Si x est égal au candidat, ajoutez 1 à count. Sinon, soustrayez 1.
Après le dernier élément, renvoyez candidate.

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for x in nums:
        if count == 0:
            candidate = x  # the old candidate's votes are used up
        if x == candidate:
            count += 1
        else:
            count -= 1  # x and one copy of the candidate cancel out
    return candidate

Pièges et cas limites

La plupart des mauvaises réponses viennent de la limite à la moitié ou d’une interprétation excessive du compteur.

« Plus de la moitié » est une condition stricte. count >= n / 2 accepte 2 occurrences sur 4, ce qui ne constitue pas une majorité. Compare plutôt avec count * 2 > n : aucun arrondi ne peut alors fausser le résultat.
La valeur finale de count dans Boyer-Moore n’indique pas le nombre d’occurrences de l’élément majoritaire. Pour [8, 8, 1, 1, 8, 1, 8], elle finit à 1, alors que 8 apparaît quatre fois.
Commencer par candidate = nums[0] et count = 1 ne fonctionne que si la boucle commence ensuite à l’indice 1. Si elle commence à l’indice 0, le premier élément vote deux fois : avec [1, 2, 2], le compteur finit à 0 et vous renvoyez 1.
Boyer-Moore repose sur la garantie qu’il existe une majorité. Avec [1, 2, 3], qui n’a pas de majorité, l’algorithme renvoie quand même 3. Si l’entrée ne contient pas nécessairement de majorité, comptez les occurrences du candidat en un deuxième passage avant de lui faire confiance.

Questions fréquentes4

Qu’est-ce que l’algorithme de vote de Boyer-Moore ?

Il trouve la valeur qui apparaît dans plus de la moitié d’une liste en un seul passage avec une mémoire O(1). Il conserve un candidat et un compteur : un élément identique ajoute un, un élément différent soustrait un, et lorsque le compteur atteint 0, l’élément suivant devient le candidat. Comme la majorité est plus nombreuse que toutes les autres valeurs réunies, c’est le candidat qui reste à la fin.

Quelle est la complexité temporelle et spatiale de l’élément majoritaire ?

Le vote de Boyer-Moore s’exécute en O(n) et utilise O(1) d’espace supplémentaire. Le comptage à l’aide d’une table de hachage prend également O(n), mais nécessite O(n) d’espace pour les comptes. Le tri préalable prend O(n log n).

Peut-on résoudre le problème de l’élément majoritaire en triant ?

Oui. Après le tri, toutes les copies de l’élément majoritaire se trouvent dans un même bloc de longueur supérieure à la moitié du tableau, et tout bloc de ce type couvre la position centrale. L’élément à l’indice n / 2, arrondi à l’entier inférieur, est donc la réponse. C’est court à écrire, mais cela coûte O(n log n) en temps.

Que faire si le tableau ne contient peut-être pas d’élément majoritaire ?

Boyer-Moore renvoie toujours un candidat, même lorsqu’aucune valeur ne remplit plus de la moitié du tableau. Ajoute une deuxième passe qui compte les occurrences du candidat et accepte-le uniquement si le nombre est supérieur à n / 2. La complexité totale reste de O(n) en temps et de O(1) en espace.

Python

def majorityElement(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

nums = [3, 9, 3, 3, 4]

Attendu