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

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é

Algorithme
Python

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.

Algorithme
Python

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)

Elément majoritaire d'un tableau