The Boyer-Moore balsošana algoritms ir viens no populārākajiem optimālajiem algoritmiem, ko izmanto, lai atrastu vairākuma elementu starp dotajiem elementiem, kuriem ir vairāk nekā N/2 gadījumi. Tas darbojas lieliski, lai atrastu vairākuma elementu, kas veic 2 šķērsojumus pa dotajiem elementiem, kas darbojas O(N) laika sarežģītībā un O(1) telpas sarežģītībā.
svm
Ļaujiet mums redzēt algoritmu un intuīciju aiz tā darbības, ņemot piemēru -
Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1> Šis algoritms darbojas, pamatojoties uz to, ka, ja elements parādās vairāk nekā N/2 reizes, tas nozīmē, ka pārējie elementi, izņemot šo, noteikti būtu mazāki par N/2. Tātad, pārbaudīsim algoritma darbību.
- Vispirms izvēlieties kandidātu no dotās elementu kopas, ja tas ir tāds pats kā kandidāta elements, palieliniet balsu skaitu. Pretējā gadījumā samaziniet balsu skaitu, ja balsis kļūst par 0, kā jauno kandidātu atlasiet citu jaunu elementu.
Intuīcija aiz darba:
Ja elementi ir tādi paši kā kandidāta elements, balsis tiek palielinātas, turpretim, ja tiek atrasts kāds cits elements (kas nav vienāds ar kandidāta elementu), mēs samazinājām skaitu. Tas faktiski nozīmē, ka mēs samazinām izvēlētā kandidāta uzvaras spēju prioritāti, jo mēs zinām, ka, ja kandidāts ir vairākumā, tas notiek vairāk nekā N/2 reizes un atlikušie elementi ir mazāki par N/2. Mēs turpinām samazināt balsu skaitu, jo esam atraduši dažus elementus, kas atšķiras no kandidāta elementa. Kad balsu skaits kļūst par 0, tas faktiski nozīmē, ka par dažādiem elementiem ir vienāds balsu skaits, kam nevajadzētu būt gadījumā, ja elements ir vairākuma elements. Tātad kandidāta elements nevar būt vairākums, un tāpēc mēs izvēlamies pašreizējo elementu kā kandidātu un turpinām to pašu, līdz visi elementi ir pabeigti. Galīgais kandidāts būtu mūsu vairākuma elements. Mēs pārbaudām, izmantojot 2. šķērsošanu, lai redzētu, vai tā skaits ir lielāks par N/2. Ja tā ir taisnība, mēs to uzskatām par vairākuma elementu.
Darbības algoritma ieviešanai:
1. darbība — Atrodi kandidātu ar vairākumu –
- Inicializējiet mainīgo vārdu i ,balsis = 0, kandidāts =-1
- Šķērsojiet masīvu, izmantojot cilpu
- Ja balsis = 0, Izvēlies kandidāts = arr[i] , veidot balsis=1 .
- citādi, ja pašreizējais elements ir tāds pats kā kandidāta balsu pieaugums
- citādi samazināt balsis.
2. darbība — Pārbaudiet, vai kandidātam ir vairāk par N/2 balsīm –
- Inicializējiet mainīgo skaitu =0 un palieliniet skaitu, ja tas ir tāds pats kā kandidātam.
- Ja skaits ir>N/2, atgrieziet kandidātu.
- citādi atgriešanās -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 Tātad 1 ir vairākuma elements.>
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) atgriešanās kandidāts; atgriešanās -1; } int main() { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = izmērs(arr) / izmērs(arr[0]); int vairākums = atrastMajority(arr, n); cout<< ' The majority element is : ' << majority; return 0; }> |
java lasīt csv
>
>
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)) atgriešanās kandidāts; atgriešanās -1; // Pēdējo for cilpu un if priekšraksta soli var // izlaist, ja ir apstiprināts, ka vairākuma elements // ir masīvā, tikai atgriež kandidātu // tādā gadījumā } // Draivera kods public static void main(String[ ] args) { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int vairākums = atrastMajority(arr); System.out.println(' Vairākuma elements ir: ' + vairākums); } } // Šis kods ir 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> |
Sridevi
>
>
C#
apakšvirknes metode java
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)) atgriešanās kandidāts; atgriešanās -1; // Pēdējo for cilpu un if priekšraksta soli var // izlaist, ja ir apstiprināts, ka vairākuma elements // ir masīvā, tikai atgriež kandidātu // tādā gadījumā } // Draivera kods public static void Main(String[ ] args) { int []arr = { 1, 1, 1, 1, 2, 3, 4}; int vairākums = atrastMajority(arr); Console.Write(' Vairākuma elements ir: ' + vairākums); } } // Šo kodu ir sagatavojis 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)) atgriešanās kandidāts; atgriešanās -1; // Pēdējo for cilpu un if priekšraksta soli var // izlaist, ja ir apstiprināts, ka vairākuma elements // atrodas masīvā, tikai atgriež kandidātu // tādā gadījumā } // Draiveris var arr = [ 1, 1 , 1, 1, 2, 3, 4 ]; var vairākums = atrastMajority(arr); document.write(' Vairākuma elements ir: ' + vairākums); // Šo kodu ir sagatavojis shivanisinghss2110.>> |
>java virkne isemptyThe majority element is : 1>
Laika sarežģītība: O(n) (divām pārejām pa masīvu )
Kosmosa sarežģītība: O(1)