Elément majoritaire d'un tableau
Ecrivez 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 (et il existe donc au plus un de ces éléments). Exemple : A= [2, 6, 2, 2, 6, 2, 2, 8, 2, 1] (n=10) L’élément 2 apparait plus que 5 fois
Solution 1 : Naive
Utiliser deux boucles
dans la boucle intérieure calculer le nombre d'occurences de chaque élément dans la boucle extérieure verifier si le nombre d'occurence est supérieur à taille/2, et retourner cet élément pour i=1 à n cpt=0 pour j=1 à n SI tab[j]=tab[i] alors cpt=cpt+1 SI cpt>=(n/2) alors retourner tab[i] retourner NIL
Complexité O(n2)
def majoritaire(tab): 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
Solution 2 : Tableau trié
Utiliser un tableau trié
1 - Trier le tableau 2 - Parcourir le tableau et compter le nombre d'occurences 3 - si le nombre d'occurences d'un élément est supérieur à taille/2, retourner cet élément 4 - Retourner NIL Sinon.
Complexité de tri est O(nlogn) avec le tri rapide
Complexité de la boucle est O(n)
Donc complexité de cet algorithme est O(nlogn)
def majoritaire(tab): n=len(tab) cpt=1 indice=0 for i in range(1,n): if cpt>(n//2): return tab[indice] if tab[i]==tab[indice]: cpt+=1 else: # si tab[i] est différent de tab[indice] indice=i; cpt=1 return None
Solution 3 : Algorithme de Boyer–Moore
Cette méthode ne fonctionne que lorsque cet élément majoritaire existe dans le tableau. Sinon, cette méthode ne fonctionnera pas
l'algorithme est décomposé en deux étapes :- La première étape donne l'élément qui peut être un élément majoritaire dans le tableau. S'il y a un élément majoritaire dans un tableau, cette étape renverra définitivement l'élément majoritaire, sinon elle retournera un candidat pour l'élément majoritaire.
- Vérifiez si l'élément obtenu à partir de l'étape 1 est un élément majoritaire. Cette étape est nécessaire car nous ne sommes pas toujours sûrs que l'élément renvoyé par la première étape est un élément majoritaire.
Etape 1 :
1 - Initialiser le compteur pour le candidat à 0 2 - Parcourir le Tableau 2-1 - SI compteur=0 alors candidat=tab[i]; compteur+=1 2-2 - SINON 2-2-1 - SI candidat=tab[i] ALORS compteur+=1 2-2-1 SINON compteur-=1
cette étape consiste à parcourir le tableau et maintient le compteur pour le candidat.
- Si l'élément suivant est identique, incrémentez le compteur,
- si l'élément suivant n'est pas identique, décrémentez-le et
- si le nombre atteint 0, modifiez le candidat en élément actuel et réinitialiser le compteur
Etape 2 :
1 - SI compteur=0 ALORS pas d'element majoritaire 2 - SINON 2-1 - parcourir le tableau et compteur le nombre d'occurences pour le candidat 2-2 - SI compteur > n/2 ALORS retourner candidat 2-3 - ELSE retourner NIL
Complexité : O(n)
# ETAPE 1 def TrouverCandidat(A): n=len(A) cand_indice = 0 compteur = 1 for i in range(n): if A[cand_indice] == A[i]: compteur += 1 else: compteur -= 1 if count == 0: cand_indice = i compteur = 1 return A[cand_indice] # ETAPE 2 def estMajoritaire(A, cand): n=len(A) compteur = 0 for i in range(n): if A[i] == cand: compteur += 1 if compteur > len(A)/2: return True else: return False # TEST def Majoritaire(A): # Trouver un candidat cand = TrouverCandidat(A) # Afficher l'élément majoritaire s'il exist if estMajoritaire(A, cand) == True: print(cand) else: print("Pas d'élément majoritaire") A = [1, 3, 3, 1, 2] Majoritaire(A)
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa