De Boyer-Moore stemmer Algoritmen er en av de populære optimale algoritmene som brukes til å finne majoritetselementet blant de gitte elementene som har mer enn N/2 forekomster. Dette fungerer helt greit for å finne majoritetselementet som tar 2 traverseringer over de gitte elementene, som fungerer i O(N) tidskompleksitet og O(1) romkompleksitet.
La oss se algoritmen og intuisjonen bak dens virkemåte, ved å ta et eksempel –
Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1> Denne algoritmen fungerer på det faktum at hvis et element forekommer mer enn N/2 ganger, betyr det at de gjenværende elementene enn dette definitivt vil være mindre enn N/2. Så la oss sjekke forløpet til algoritmen.
c kodearray av strenger
- Først velger du en kandidat fra det gitte settet med elementer hvis det er det samme som kandidatelementet, øker stemmene. Ellers reduserer du stemmene hvis stemmene blir 0, velg et annet nytt element som ny kandidat.
Intuisjon bak arbeid:
Når elementene er de samme som kandidatelementet, økes stemmene, mens når et annet element er funnet (ikke lik kandidatelementet), reduserte vi antallet. Dette betyr faktisk at vi reduserer prioriteringen av vinnerevnen til den valgte kandidaten, siden vi vet at hvis kandidaten er i flertall skjer det mer enn N/2 ganger og de gjenværende elementene er mindre enn N/2. Vi fortsetter å redusere stemmene siden vi fant noen andre elementer enn kandidatelementet. Når stemmer blir 0, betyr dette faktisk at det er like mange stemmer for ulike elementer, noe som ikke bør være tilfellet for at elementet skal være flertallselementet. Så kandidatelementet kan ikke være flertallet, og derfor velger vi det nåværende elementet som kandidat og fortsetter det samme til alle elementene er ferdige. Den endelige kandidaten ville være vårt flertallselement. Vi sjekker ved å bruke den andre traverseringen for å se om antallet er større enn N/2. Hvis det er sant, anser vi det som flertallselementet.
Trinn for å implementere algoritmen:
Trinn 1 - Finn en kandidat med flertall –
- Initialiser en variabel si i ,stemmer = 0, kandidat =-1
- Gå gjennom matrisen med for loop
- Hvis stemmer = 0, Velg kandidat = arr[i] , gjøre stemmer=1 .
- annet hvis det gjeldende elementet er det samme som kandidatens økende stemmer
- ellers reduserer stemmene.
Steg 2 - Sjekk om kandidaten har mer enn N/2 stemmer –
- Initialiser et variabelantall =0 og øke antallet hvis det er det samme som kandidaten.
- Hvis antallet er>N/2, returner kandidaten.
- ellers returnerer -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 Så 1 er majoritetselementet.>
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) returkandidat; returnere -1; } int main() { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = størrelse på(arr) / størrelse på(arr[0]); int majoritet = finnMajority(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)) returkandidat; returnere -1; // Det siste for-løkken og if-setningstrinnet kan // hoppes over hvis et majoritetselement bekreftes til // være tilstede i en matrise, bare returner kandidat // i så fall } // Driverkode offentlig statisk void main(String[ ] args) { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int majoritet = finnMajority(arr); System.out.println(' Majoritetselementet er: ' + majoritet); } } // Denne koden er bidratt av Arnav Sharma> |
>
>
imessage-spill på Android
Python3
# 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#
konvertere en streng til dato
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>(antall.Lengde / 2)) returkandidat; returnere -1; // Den siste for-løkken og if-setningstrinnet kan // hoppes over hvis et majoritetselement bekreftes til å // være tilstede i en matrise, bare returner kandidat // i så fall } // Driverkode offentlig statisk void Main(String[ ] args) { int []arr = { 1, 1, 1, 1, 2, 3, 4}; int majoritet = finnMajority(arr); Console.Write(' Majoritetselementet er: ' + majoritet); } } // Denne koden er bidratt av 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)) returkandidat; returnere -1; // Det siste for løkke og if-setningstrinnet kan // hoppes over hvis et majoritetselement bekreftes til å // være tilstede i en matrise, bare returner kandidat // i så fall } // Driverkode var arr = [ 1, 1 , 1, 1, 2, 3, 4]; var majoritet = finnMajority(arr); document.write(' Majoritetselementet er: ' + majoritet); // Denne koden er bidratt av shivanisinghss2110.> |
>
>
java program loopProduksjon
The majority element is : 1>
Tidskompleksitet: O(n) (For to passeringer over matrisen)
Plass kompleksitet: O(1)