The Hlasovanie Boyer-Moore Algoritmus je jedným z populárnych optimálnych algoritmov, ktorý sa používa na nájdenie väčšinového prvku medzi danými prvkami, ktoré majú viac ako N/2 výskytov. Toto funguje úplne dobre na nájdenie väčšinového prvku, ktorý má 2 prechody cez dané prvky, čo funguje v časovej zložitosti O(N) a priestorovej zložitosti O(1).
Pozrime sa na algoritmus a intuíciu za jeho fungovaním na príklade –
Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1> Tento algoritmus pracuje na tom, že ak sa prvok vyskytuje viac ako N/2-krát, znamená to, že ostatné prvky okrem tohto by určite boli menšie ako N/2. Pozrime sa teda na priebeh algoritmu.
- Najprv vyberte kandidáta z daného súboru prvkov, ak je rovnaký ako prvok kandidáta, zvýšte hlasy. V opačnom prípade znížte hlasy, ak sa hlasy stanú 0, ako nového kandidáta vyberte iný nový prvok.
Intuícia za prácou:
Keď sú prvky rovnaké ako prvok kandidáta, hlasy sa zvýšia, zatiaľ čo keď sa nájde nejaký iný prvok (nerovná sa prvku kandidáta), znížime počet. To vlastne znamená, že znižujeme prioritu víťaznej schopnosti vybraného kandidáta, keďže vieme, že ak je kandidát vo väčšine, vyskytuje sa viac ako N/2-krát a zvyšné prvky sú menej ako N/2. Neustále znižujeme hlasy, pretože sme našli nejaký iný prvok (prvky) ako prvok kandidáta. Keď sa hlasy stanú 0, znamená to v skutočnosti, že existuje rovnaký počet hlasov pre rôzne prvky, čo by nemalo platiť v prípade, že prvok je väčšinovým prvkom. Kandidátsky prvok teda nemôže byť väčšina, a preto volíme súčasný prvok ako kandidáta a pokračujeme v tom istom, až kým sa nedokončia všetky prvky. Konečný kandidát by bol naším väčšinovým prvkom. Pomocou 2. prechodu skontrolujeme, či je jeho počet väčší ako N/2. Ak je to pravda, považujeme to za väčšinový prvok.
Kroky na implementáciu algoritmu:
Krok 1 - Nájdite kandidáta s väčšinou –
- Povedzme inicializáciu premennej i ,hlasy = 0, kandidát =-1
- Prejdite cez pole pomocou cyklu for
- Ak hlasy = 0, vyber kandidát = arr[i] , urobiť hlasy = 1 .
- inak, ak je aktuálny prvok rovnaký ako prírastok hlasov kandidáta
- inak znížte hlasy.
Krok 2 - Skontrolujte, či má kandidát viac ako N/2 hlasov –
stojace
- Inicializujte počet premenných = 0 a zvýšte počet, ak je rovnaký ako kandidát.
- Ak je počet>N/2, vráťte kandidáta.
- inak vrátiť -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 Takže 1 je väčšinový prvok.>
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) vrátiť kandidáta; návrat -1; } int main() { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int väčšina = nájsť väčšinu(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>(číslo.dĺžka / 2)) vrátiť kandidáta; návrat -1; // Posledný cyklus for a krok príkazu if možno // preskočiť, ak je potvrdené, že väčšinový prvok // je prítomný v poli, stačí vrátiť kandidáta // v takom prípade } // Kód ovládača public static void main(String[ ] args) { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int väčšina = findMajority(arr); System.out.println(' Prvok väčšiny je: ' + väčšina); } } // Tento kód pridal Arnav Sharma> |
>
>
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#
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>(čísla.Dĺžka / 2)) vrátiť kandidáta; návrat -1; // Posledný cyklus for a krok príkazu if možno // preskočiť, ak sa potvrdí, že väčšinový prvok // je prítomný v poli, stačí vrátiť kandidáta // v takom prípade } // Kód ovládača public static void Main(String[ ] args) { int []arr = { 1, 1, 1, 1, 2, 3, 4}; int väčšina = findMajority(arr); Console.Write(' Prvok väčšiny je: ' + väčšina); } } // Tento kód prispel shivanisinghss2110> |
>
>
java previesť reťazec na celé číslo
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>(číslo.dĺžka / 2)) vrátiť kandidáta; návrat -1; // Posledný cyklus for a krok príkazu if možno // preskočiť, ak sa potvrdí, že väčšinový prvok // bude prítomný v poli, stačí vrátiť kandidáta // v takom prípade } // Kód ovládača var arr = [ 1, 1 1, 1, 2, 3, 4]; var väčšina = nájsť väčšinu(arr); document.write(' Prvok väčšiny je: ' + väčšina); // Tento kód prispel shivanisinghss2110.> |
>
>Výkon
The majority element is : 1>
Časová zložitosť: O(n) (pre dva prechody cez pole)
Priestorová zložitosť: O(1)