Majority Element

Q: Et si le tableau ne contenait pas d’élément majoritaire ?

Boyer-Moore renvoie toujours un candidat : sur [1, 2, 3] , il renvoie 3. Ajoutez une deuxième passe qui compte les occurrences du candidat et acceptez-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.

FacileHachage

+10

Vous obtenez un tableau d’entiers nums de longueur n. Une valeur y apparaît plus de n / 2 fois, et cette valeur est appelée l’élément majoritaire. Retournez-la. Une valeur qui occupe plus de la moitié du tableau est toujours unique : il existe donc 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 une fois chacun.

Pour aller plus loin

Peux-tu trouver chaque valeur qui apparaît plus de n / 3 fois, en O(n) avec O(1) mémoire supplémentaire ?

Solution

La valeur majoritaire est plus fréquente que toutes les autres valeurs réunies. Éliminez des paires de valeurs différentes : certaines de ses occurrences survivront toujours. Le vote de Boyer-Moore effectue ces appariements en un seul passage avec un candidat et un compteur ; vous n’avez donc pas besoin d’une table de hachage des occurrences.

Compter avec une table de hachage

Intuition

Comptez chaque valeur dans une table de hachage et renvoyez la première valeur dont le nombre dépasse la moitié de la longueur. Pour [3, 9, 3, 3, 4], le nombre de 3 atteint 3 à l’indice 3, soit plus de 2.5, vous renvoyez donc la valeur avant de lire le 4.

Chaque recherche est en O(1) en moyenne, donc le temps est en O(n), mais la table peut contenir environ n / 2 valeurs différentes : O(n) en mémoire.

Algorithme

Créez une map vide associant chaque valeur à son nombre d’occurrences.
Pour chaque élément x, ajoutez 1 au nombre d’occurrences de x.
Si ce nombre d’occurrences multiplié par 2 est supérieur à la longueur du tableau, renvoyez 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

Conserve un candidate et un count de ses votes qui n’ont pas encore été 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. Lorsque le compte atteint 0, l’élément suivant devient le candidat.

Chaque annulation élimine deux valeurs différentes, donc au plus une copie de la valeur majoritaire. Si la valeur majoritaire apparaît m fois, les autres n - m éléments sont moins nombreux que m et ne peuvent pas annuler toutes ses copies. Tous les votes encore présents à la fin appartiennent au candidat final, et une copie de la valeur majoritaire en fait partie.

Pour [8, 8, 1, 1, 8, 1, 8], le compte passe à 1, 2, 1, 0, car les 1 annulent les deux 8. Le 8 suivant relance le compte à 1, le 1 suivant l’annule, et le dernier 8 redevient le candidat. Un seul parcours avec deux variables offre un temps O(n) et une mémoire O(1).

Algorithme

Définissez candidate comme le 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

« Plus de la moitié » est strict. count >= n / 2 accepte 2 occurrences sur 4, ce qui ne constitue pas une majorité. Comparez count * 2 > n : aucun arrondi ne vient alors fausser le résultat.
Lire le count final comme la fréquence de l’élément majoritaire. Pour [8, 8, 1, 1, 8, 1, 8], il se termine à 1, alors que 8 apparaît quatre fois.
Commencer avec candidate = nums[0] et count = 1, puis parcourir la liste à partir de l’indice 0. Le premier élément vote deux fois : avec [1, 2, 2], le compte se termine à 0 et vous renvoyez 1.

Questions fréquentes3

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

Le vote de Boyer-Moore s’exécute en temps O(n) et utilise O(1) espace supplémentaire. Le comptage à l’aide d’une table de hachage s’exécute également en temps O(n), mais nécessite O(n) espace pour les comptages. Le tri préalable prend un temps 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 occurrences 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’index n / 2, arrondi à l’entier inférieur, est donc la réponse, pour un coût de O(n log n) en temps.

Et si le tableau ne contenait pas d’élément majoritaire ?

Boyer-Moore renvoie toujours un candidat : sur [1, 2, 3], il renvoie 3. Ajoutez une deuxième passe qui compte les occurrences du candidat et acceptez-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.

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

Test #1

Test #2

Argument

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

Résultat attendu