Problème de l'élément majoritaire
Un élément majoritaire dans un tableau A de taille n est un élément qui apparaît plus de n/2 fois (il existe donc au plus un tel élément).
A = [2, 6, 2, 2, 6, 2, 2, 8, 2, 1]
2
Trouver l'élément majoritaire
Écrivez un algorithme qui prend un tableau et affiche l'élément majoritaire (s'il existe), sinon retourner NIL.
Un élément majoritaire dans un tableau A de taille n est un élément qui apparaît plus de n/2 fois.
Solution 1 : Approche naïve (O(n²))
Utiliser deux boucles imbriquées :
pour i de 1 à n:
cpt = 0
pour j de 1 à n:
si tab[j] = tab[i] alors
cpt = cpt + 1
si cpt > (n/2) alors
retourner tab[i]
retourner NILComplexité : O(n²)
def majoritaire_naif(tab):
"""
Recherche naïve de l'élément majoritaire
Complexité : O(n²)
"""
n = len(tab)
for i in range(n):
cpt = 0
for j in range(n):
if tab[i] == tab[j]:
cpt += 1
if cpt > (n // 2):
return tab[i]
return None
# Test
A = [2, 6, 2, 2, 6, 2, 2, 8, 2, 1]
print(f"Majoritaire (naïf) : {majoritaire_naif(A)}")Solution 2 : Tableau trié (O(n log n))
1 - Trier le tableau (O(n log n))
2 - Parcourir le tableau et compter le nombre d'occurrences
3 - Si le nombre d'occurrences d'un élément est > n/2, retourner cet élément
4 - Retourner NIL sinonComplexité : O(n log n) pour le tri, O(n) pour le parcours → O(n log n) total
def majoritaire_trie(tab):
"""
Recherche de l'élément majoritaire avec un tableau trié
Complexité : O(n log n)
"""
n = len(tab)
if n == 0:
return None
tab_trie = sorted(tab)
cpt = 1
indice = 0
for i in range(1, n):
if cpt > (n // 2):
return tab_trie[indice]
if tab_trie[i] == tab_trie[indice]:
cpt += 1
else:
indice = i
cpt = 1
# Vérifier le dernier élément
if cpt > (n // 2):
return tab_trie[indice]
return None
A = [2, 6, 2, 2, 6, 2, 2, 8, 2, 1]
print(f"Majoritaire (trié) : {majoritaire_trie(A)}")Solution 3 : Algorithme de Boyer–Moore (O(n))
Cette méthode ne fonctionne que lorsque l'élément majoritaire existe dans le tableau. L'algorithme est décomposé en deux étapes :
- Étape 1 : Trouver un candidat potentiel pour l'élément majoritaire.
- Étape 2 : Vérifier si ce candidat est effectivement majoritaire.
Étape 1 : Recherche du candidat
L'idée est de parcourir le tableau en maintenant un compteur pour un candidat :
- Si le compteur est 0, on choisit l'élément courant comme nouveau candidat.
- Si l'élément suivant est identique au candidat, on incrémente le compteur.
- Si l'élément suivant est différent, on décrémente le compteur.
Étape 2 : Vérification
On parcourt le tableau pour compter le nombre d'occurrences du candidat. Si ce nombre est > n/2, on retourne le candidat, sinon on retourne NIL.
Étape 1 : Trouver un candidat
Initialiser compteur = 0, candidat = None
Pour chaque élément x du tableau:
si compteur == 0:
candidat = x
compteur = 1
sinon:
si x == candidat:
compteur += 1
sinon:
compteur -= 1Étape 2 : Vérifier le candidat
Compter le nombre d'occurrences de candidat dans le tableau
si occurrences > n/2:
retourner candidat
sinon:
retourner NILComplexité : O(n) temps, O(1) espace
def trouver_candidat(A):
"""
Étape 1 : Trouve un candidat potentiel pour l'élément majoritaire
"""
n = len(A)
cand_indice = 0
compteur = 1
for i in range(1, n):
if A[cand_indice] == A[i]:
compteur += 1
else:
compteur -= 1
if compteur == 0:
cand_indice = i
compteur = 1
return A[cand_indice]
def est_majoritaire(A, cand):
"""
Étape 2 : Vérifie si le candidat est effectivement majoritaire
"""
n = len(A)
compteur = 0
for x in A:
if x == cand:
compteur += 1
return compteur > n // 2
def majoritaire_boyer_moore(A):
"""
Algorithme de Boyer-Moore pour trouver l'élément majoritaire
Complexité : O(n) temps, O(1) espace
"""
if not A:
return None
# Étape 1 : Trouver un candidat
cand = trouver_candidat(A)
# Étape 2 : Vérifier le candidat
if est_majoritaire(A, cand):
return cand
else:
return None
# Tests
A1 = [2, 6, 2, 2, 6, 2, 2, 8, 2, 1]
A2 = [1, 3, 3, 1, 2]
A3 = [1, 2, 3, 4, 5]
print(f"Test 1 - {A1} : {majoritaire_boyer_moore(A1)}")
print(f"Test 2 - {A2} : {majoritaire_boyer_moore(A2)}")
print(f"Test 3 - {A3} : {majoritaire_boyer_moore(A3)}")Test 1 - [2, 6, 2, 2, 6, 2, 2, 8, 2, 1] : 2 Test 2 - [1, 3, 3, 1, 2] : None Test 3 - [1, 2, 3, 4, 5] : None
L'algorithme de Boyer-Moore repose sur le principe suivant : si on élimine des paires d'éléments différents, l'élément majoritaire (s'il existe) restera à la fin.
C'est pourquoi on peut maintenir un compteur :
- Quand on voit le même élément que le candidat, on augmente le compteur (on "ajoute" un élément).
- Quand on voit un élément différent, on diminue le compteur (on "élimine" une paire).
Comparaison des approches
| Approche | Complexité temporelle | Complexité spatiale | Avantages / Inconvénients |
|---|---|---|---|
| Naïve (double boucle) | O(n²) | O(1) | Simple mais très inefficace pour de grands tableaux |
| Tri + parcours | O(n log n) | O(1) si tri en place, O(n) sinon | Bon compromis, facile à comprendre |
| Boyer-Moore | O(n) | O(1) | Optimal, mais nécessite une vérification |
- 1 ≤ n ≤ 10⁶
- Les éléments du tableau peuvent être de n'importe quel type comparable
- L'élément majoritaire est celui qui apparaît plus de n/2 fois.
- Il ne peut y avoir au plus qu'un seul élément majoritaire.
- L'algorithme de Boyer-Moore est optimal avec une complexité O(n).
- Après avoir trouvé un candidat, il est impératif de vérifier qu'il est bien majoritaire.
- L'approche par tri est plus simple mais moins efficace (O(n log n)).
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.