De Boyer-Moore-stemming algoritme is een van de populaire optimale algoritmen die wordt gebruikt om het meerderheidselement te vinden onder de gegeven elementen die meer dan N/2 voorkomen. Dit werkt prima voor het vinden van het meerderheidselement dat twee keer de gegeven elementen moet doorlopen, wat werkt in O(N) tijdscomplexiteit en O(1) ruimtecomplexiteit.
iets snel sorteren
Laten we het algoritme en de intuïtie achter de werking ervan zien, door een voorbeeld te nemen:
Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1> Dit algoritme werkt op basis van het feit dat als een element meer dan N/2 keer voorkomt, dit betekent dat de overige elementen anders dan dit zeker minder dan N/2 zullen zijn. Laten we dus de voortgang van het algoritme controleren.
- Kies eerst een kandidaat uit de gegeven set elementen als deze hetzelfde is als het kandidaat-element, verhoog de stemmen. Anders verlaag je het aantal stemmen als de stemmen 0 worden, en selecteer je een ander nieuw element als nieuwe kandidaat.
Intuïtie achter werken:
Wanneer de elementen hetzelfde zijn als het kandidaat-element, worden de stemmen verhoogd, terwijl wanneer een ander element wordt gevonden (niet gelijk aan het kandidaat-element), we het aantal hebben verlaagd. Dit betekent feitelijk dat we de prioriteit van het winnende vermogen van de geselecteerde kandidaat verlagen, omdat we weten dat als de kandidaat in de meerderheid is, dit meer dan N/2 keer voorkomt en dat de resterende elementen minder dan N/2 zijn. We blijven het aantal stemmen verlagen omdat we een of meer andere elementen hebben gevonden dan het kandidaat-element. Wanneer de stemmen 0 worden, betekent dit feitelijk dat er evenveel stemmen zijn voor verschillende elementen, wat niet het geval zou moeten zijn als het element het meerderheidselement zou zijn. Het kandidaat-element kan dus niet de meerderheid zijn en daarom kiezen we het huidige element als kandidaat en gaan we op dezelfde manier door totdat alle elementen klaar zijn. De uiteindelijke kandidaat zou ons meerderheidselement zijn. We controleren met behulp van de 2e doorgang om te zien of de telling groter is dan N/2. Als het waar is, beschouwen we het als het meerderheidselement.
Stappen om het algoritme te implementeren:
Stap 1 - Vind een kandidaat met de meerderheid –
- Initialiseer bijvoorbeeld een variabele i, stemmen = 0, kandidaat =-1
- Doorloop de array met behulp van de for-lus
- Als stemmen = 0, kies de kandidaat = arr[i] , maken stemmen=1 .
- anders als het huidige element hetzelfde is als de kandidaat-verhoging van stemmen
- anders stemmen verlagen.
Stap 2 - Controleer of de kandidaat meer dan N/2 stemmen heeft –
- Initialiseer een variabeletelling =0 en verhoog de telling als deze hetzelfde is als de kandidaat.
- Als de telling>N/2 is, stuurt u de kandidaat terug.
- anders retourneer -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 Dus 1 is het meerderheidselement.>
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) terugkeerkandidaat; retour -1; } int main() { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = groottevan(arr) / groottevan(arr[0]); int meerderheid = findMajority(arr, n); uit<< ' 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)) retourkandidaat; retour -1; // De laatste for-lus en de if-instructiestap kunnen // worden overgeslagen als wordt bevestigd dat een meerderheidselement aanwezig is in een array, retourneer dan gewoon de kandidaat // in dat geval } // Stuurprogrammacode public static void main(String[ ] args) { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int meerderheid = findMajority(arr); System.out.println(' Het meerderheidselement is: ' + meerderheid); } } // Deze code is bijgedragen door Arnav Sharma> |
>
>
Python3
Android-proces acore blijft stoppen
# 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.Lengte / 2)) retourkandidaat; retour -1; // De laatste for-lus en de if-instructiestap kunnen // worden overgeslagen als wordt bevestigd dat een meerderheidselement aanwezig is in een array, retourneer dan gewoon de kandidaat // in dat geval } // Stuurprogrammacode public static void Main(String[ ] args) { int []arr = { 1, 1, 1, 1, 2, 3, 4}; int meerderheid = findMajority(arr); Console.Write(' Het meerderheidselement is: ' + meerderheid); } } // Deze code is bijgedragen door shivanisinghss2110> |
>
>
Javascript
een string naar datum converteren
> // 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)) retourkandidaat; retour -1; // De laatste for-lus en de if-instructiestap kunnen // worden overgeslagen als wordt bevestigd dat een meerderheidselement aanwezig is in een array, retourneer dan gewoon de kandidaat // in dat geval } // Drivercode var arr = [ 1, 1 , 1, 1, 2, 3, 4]; var meerderheid = findMajority(arr); document.write(' Het meerderheidselement is: ' + meerderheid); // Deze code is bijgedragen door shivanisinghss2110.> |
>
>Uitvoer
The majority element is : 1>
Tijdcomplexiteit: O(n) ( Voor twee passages over de array )
Ruimtecomplexiteit: O(1)