Le Vote Boyer-Moore L'algorithme est l'un des algorithmes optimaux les plus populaires qui est utilisé pour trouver l'élément majoritaire parmi les éléments donnés qui ont plus de N/2 occurrences. Cela fonctionne parfaitement pour trouver l'élément majoritaire qui effectue 2 parcours sur les éléments donnés, qui fonctionne en complexité temporelle O(N) et en complexité spatiale O(1).
Voyons l'algorithme et l'intuition derrière son fonctionnement, en prenant un exemple –
Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1> Cet algorithme fonctionne sur le fait que si un élément apparaît plus de N/2 fois, cela signifie que les éléments restants autres que celui-ci seraient certainement inférieurs à N/2. Vérifions donc le déroulement de l'algorithme.
- Tout d'abord, choisissez un candidat parmi l'ensemble d'éléments donné, s'il est identique à l'élément candidat, augmentez les votes. Sinon, diminuez les votes si les votes deviennent 0, sélectionnez un autre nouvel élément comme nouveau candidat.
L'intuition derrière le travail :
Lorsque les éléments sont identiques à l'élément candidat, les votes sont incrémentés tandis que lorsqu'un autre élément est trouvé (non égal à l'élément candidat), nous diminuons le décompte. Cela signifie en fait que nous diminuons la priorité de la capacité gagnante du candidat sélectionné, puisque nous savons que si le candidat est majoritaire, cela se produit plus de N/2 fois et les éléments restants sont inférieurs à N/2. Nous continuons à diminuer les votes car nous avons trouvé des éléments différents de l'élément candidat. Lorsque les votes deviennent 0, cela signifie en fait qu'il y a le même nombre de votes pour les différents éléments, ce qui ne devrait pas être le cas pour que l'élément soit majoritaire. Ainsi, l’élément candidat ne peut pas être majoritaire et nous choisissons donc l’élément actuel comme candidat et continuons ainsi jusqu’à ce que tous les éléments soient terminés. Le candidat final serait notre élément majoritaire. Nous vérifions à l'aide du 2ème parcours si son décompte est supérieur à N/2. Si c’est vrai, nous le considérons comme l’élément majoritaire.
Étapes pour implémenter l'algorithme :
Étape 1 - Trouver un candidat majoritaire –
- Initialiser une variable, par exemple je, votes = 0, candidat =-1
- Parcourez le tableau en utilisant la boucle for
- Si voix = 0, choisir la candidat = arr[i] , faire votes=1 .
- sinon si l'élément actuel est le même que les votes d'incrémentation du candidat
- sinon, diminuez les votes.
Étape 2 - Vérifiez si le candidat a plus de N/2 voix –
- Initialisez un nombre de variables = 0 et incrémentez le nombre s'il est identique au candidat.
- Si le décompte est>N/2, renvoyez le candidat.
- sinon, renvoie -1.
Dry run for the above example: Given : arr[]= 1 1 1 1 2 3 5 votes =0 1 2 3 4 3 2 1 candidate = -1 1 1 1 1 1 1 1 candidate = 1 after first traversal 1 1 1 1 2 3 5 count =0 1 2 3 4 4 4 4 candidate = 1 Hence count>7/2 =3 Donc 1 est l'élément majoritaire.>
C++
// C++ implementation for the above approach> #include> using> namespace> std;> // Function to find majority element> int> findMajority(>int> arr[],>int> n)> {> >int> i, candidate = -1, votes = 0;> >// Finding majority candidate> >for> (i = 0; i if (votes == 0) { candidate = arr[i]; votes = 1; } else { if (arr[i] == candidate) votes++; else votes--; } } int count = 0; // Checking if majority candidate occurs more than n/2 // times for (i = 0; i if (arr[i] == candidate) count++; } if (count>n/2) retour candidat ; renvoie -1 ; } int main() { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = taillede(arr) / taillede(arr[0]); int majorité = findMajority(arr, n); cout<< ' The majority element is : ' << majority; return 0; }> |
>
>
Java
import> java.io.*;> class> GFG> {> >// Function to find majority element> >public> static> int> findMajority(>int>[] nums)> >{> >int> count =>0>, candidate = ->1>;> >// Finding majority candidate> >for> (>int> index =>0>; index if (count == 0) { candidate = nums[index]; count = 1; } else { if (nums[index] == candidate) count++; else count--; } } // Checking if majority candidate occurs more than // n/2 times count = 0; for (int index = 0; index if (nums[index] == candidate) count++; } if (count>(nums.length / 2)) renvoyer le candidat ; renvoie -1 ; // La dernière boucle for et l'étape de l'instruction if peuvent // être ignorées si un élément majoritaire est confirmé // être présent dans un tableau, il suffit de renvoyer le candidat // dans ce cas } // Code du pilote public static void main(String[ ] args) { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int majorité = findMajority(arr); System.out.println(' L'élément majoritaire est : ' + majorité); } } // Ce code est contribué par Arnav Sharma> |
>
>
Python3
moteur de recherche et exemples
# Python implementation for the above approach> # Function to find majority element> def> findMajority(arr, n):> >candidate>=> ->1> >votes>=> 0> > ># Finding majority candidate> >for> i>in> range> (n):> >if> (votes>=>=> 0>):> >candidate>=> arr[i]> >votes>=> 1> >else>:> >if> (arr[i]>=>=> candidate):> >votes>+>=> 1> >else>:> >votes>->=> 1> >count>=> 0> > ># Checking if majority candidate occurs more than n/2> ># times> >for> i>in> range> (n):> >if> (arr[i]>=>=> candidate):> >count>+>=> 1> > >if> (count>n>/>/> 2>):> >return> candidate> >else>:> >return> ->1> # Driver Code> arr>=> [>1>,>1>,>1>,>1>,>2>,>3>,>4> ]> n>=> len>(arr)> majority>=> findMajority(arr, n)> print>(>' The majority element is :'> ,majority)> > # This code is contributed by shivanisinghss2110> |
>
>
C#
using> System;> class> GFG> {> >// Function to find majority element> >public> static> int> findMajority(>int>[] nums)> >{> >int> count = 0, candidate = -1;> >// Finding majority candidate> >for> (>int> index = 0; index if (count == 0) { candidate = nums[index]; count = 1; } else { if (nums[index] == candidate) count++; else count--; } } // Checking if majority candidate occurs more than // n/2 times count = 0; for (int index = 0; index if (nums[index] == candidate) count++; } if (count>(nums.Length / 2)) renvoie le candidat ; renvoie -1 ; // La dernière boucle for et l'étape de l'instruction if peuvent // être ignorées si un élément majoritaire est confirmé // être présent dans un tableau, il suffit de renvoyer le candidat // dans ce cas } // Code du pilote public static void Main(String[ ] args) { int []arr = { 1, 1, 1, 1, 2, 3, 4}; int majorité = findMajority(arr); Console.Write(' L'élément majoritaire est : ' + majorité); } } // Ce code est fourni par shivanisinghss2110> |
>
>
Javascript
> // Function to find majority element> function> findMajority(nums)> >{> >var> count = 0, candidate = -1;> >// Finding majority candidate> >for> (>var> index = 0; index if (count == 0) { candidate = nums[index]; count = 1; } else { if (nums[index] == candidate) count++; else count--; } } // Checking if majority candidate occurs more than // n/2 times count = 0; for (var index = 0; index if (nums[index] == candidate) count++; } if (count>(nums.length / 2)) renvoyer le candidat ; renvoie -1 ; // La dernière boucle for et l'étape de l'instruction if peuvent // être ignorées si un élément majoritaire est confirmé // être présent dans un tableau, il suffit de renvoyer le candidat // dans ce cas } // Code du pilote var arr = [ 1, 1 , 1, 1, 2, 3, 4 ]; var majorité = findMajority(arr); document.write(' L'élément majoritaire est : ' + majorité); // Ce code est fourni par shivanisinghss2110.> |
>
>Sortir
git paiement
The majority element is : 1>
Complexité temporelle : O(n) ( Pour deux passages sur le tableau )
Complexité spatiale : O(1)