The Boyer-Moore balsavimas algoritmas yra vienas iš populiariausių optimalių algoritmų, kuris naudojamas norint rasti daugumą elementų tarp pateiktų elementų, kurie turi daugiau nei 2 atvejų. Tai puikiai veikia ieškant daugumos elemento, kuris 2 kartus pereina per nurodytus elementus, kuris veikia O(N) laiko sudėtingumu ir O(1) erdvės sudėtingumu.

Pažiūrėkime, koks jo veikimo algoritmas ir intuicija, paimdami pavyzdį –

 Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1>

Šis algoritmas veikia tuo, kad jei elementas atsiranda daugiau nei N/2 karto, tai reiškia, kad likę elementai, išskyrus tai, tikrai būtų mažesni nei N/2. Taigi patikrinkime algoritmo eigą.

• Pirmiausia pasirinkite kandidatą iš pateikto elementų rinkinio, jei jis sutampa su kandidato elementu, padidinkite balsus. Kitu atveju sumažinkite balsų skaičių, jei balsai tampa 0, kaip naują kandidatą pasirinkite kitą naują elementą.

Intuicija už darbą:
Kai elementai yra tokie patys kaip kandidato elementas, balsai didinami, o kai randamas kitas elementas (nelygus kandidato elementui), sumažinome skaičių. Tai iš tikrųjų reiškia, kad mes mažiname pasirinkto kandidato laimėjimų prioritetą, nes žinome, kad jei kandidatas yra daugumoje, tai pasitaiko daugiau nei N/2 karto, o likę elementai yra mažesni nei N/2. Mes nuolat mažiname balsų skaičių, nes radome kitokį (-ius) elementą (-ius) nei kandidato elementas. Kai balsai tampa 0, tai iš tikrųjų reiškia, kad už skirtingus elementus yra vienodas balsų skaičius, o tai neturėtų būti tuo atveju, kai elementas yra daugumos elementas. Taigi kandidato elementas negali būti dauguma, todėl dabartinį elementą pasirenkame kaip kandidatą ir tęsiame tą patį, kol baigsis visi elementai. Galutinis kandidatas būtų mūsų daugumos elementas. Naudodami 2-ąjį perėjimą patikriname, ar jo skaičius yra didesnis nei N/2. Jei tai tiesa, mes tai laikome daugumos elementu.

Algoritmo įgyvendinimo žingsniai:
1 žingsnis - Rasti kandidatą, turintį daugumą –

• Inicijuokite kintamąjį žodį i ,balsų = 0, kandidatas =-1
• Pereikite per masyvą naudodami for kilpą
• Jeigu balsai = 0, Pasirink kandidatas = arr[i] , pagaminti balsai = 1 .
• kitu atveju, jei dabartinis elementas yra toks pat kaip kandidato balsų padidėjimas
• kitu atveju sumažinkite balsus.

2 žingsnis - Patikrinkite, ar kandidatas turi daugiau nei 2 balsų –

• Inicijuokite kintamųjų skaičių =0 ir padidinkite skaičių, jei jis toks pat kaip kandidatas.
• Jei skaičius>N/2, grąžinkite kandidatą.
• kitaip grąža -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 Taigi 1 yra daugumos elementas.>

C++

skaitytuvas.next java

>

>

Java

kaip įšvirkšti abstrakčią klasę

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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>(skaičiai.Ilgis / 2)) sugrįžti kandidatas;  grąža -1;  // Paskutinis for ciklas ir if sakinio veiksmas gali būti // praleisti, jei patvirtinama, kad daugumos elementas // būti masyve, tiesiog grąžinkite kandidatą // tokiu atveju } // Tvarkyklės kodas public static void Main(String[ ] args) { int []arr = { 1, 1, 1, 1, 2, 3, 4};  int dauguma = rastiMajority(arr);  Console.Write(' Daugumos elementas yra : ' + dauguma);  } } // Šį kodą sukūrė shivanisinghss2110>
 
 
 
 
    
 
>
 
    
 
>
 
 
Javascript
    
 
     
  
 
    
 
     
     
    
 
Java vietinė data
 
 
 
 
 > // 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>(skaičiai.ilgis / 2)) sugrįžti kandidatas;  grąža -1;  // Paskutinis for ciklas ir if sakinio veiksmas gali būti // praleisti, jei patvirtinama, kad daugumos elementas // būti masyve, tiesiog grąžinti kandidatą // tokiu atveju } // Tvarkyklės kodas var arr = [ 1, 1 , 1, 1, 2, 3, 4 ];  var dauguma = rastiMajority(arr);  document.write(' Daugumos elementas yra: ' + dauguma);   // Šį kodą sukūrė shivanisinghss2110.>>
 
 
 
 
    
 
> 
    
  The majority element is : 1>
 
  Laiko sudėtingumas: O(n) (Dviem perėjimams per masyvą) 
  Erdvės sudėtingumas: O(1)