El Votació Boyer-Moore L'algoritme és un dels algorismes òptims populars que s'utilitza per trobar l'element majoritari entre els elements donats que tenen més de N/2 ocurrències. Això funciona perfectament per trobar l'element majoritari que fa 2 recorreguts sobre els elements donats, que funciona en complexitat temporal O (N) i complexitat espacial O (1).

Vegem l'algorisme i la intuïció darrere del seu funcionament, prenent un exemple:

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

Aquest algorisme funciona en el fet que si un element apareix més de N/2 vegades, vol dir que la resta d'elements diferents d'aquest seria definitivament inferior a N/2. Per tant, comprovem el funcionament de l'algorisme.

• Primer, trieu un candidat del conjunt d'elements donat si és el mateix que l'element candidat, augmenta els vots. En cas contrari, reduïu els vots si els vots passen a 0, seleccioneu un altre element nou com a nou candidat.

Intuïció darrere del treball:
Quan els elements són els mateixos que l'element candidat, els vots s'incrementen, mentre que quan es troba algun altre element (no igual a l'element candidat), disminuïm el recompte. En realitat, això vol dir que estem disminuint la prioritat de la capacitat guanyadora del candidat seleccionat, ja que sabem que si el candidat és majoritari es produeix més de N/2 vegades i la resta d'elements són inferiors a N/2. Seguim disminuint els vots ja que hem trobat algun element(s) diferent a l'element candidat. Quan els vots es converteixen en 0, això significa en realitat que hi ha el mateix nombre de vots per a diferents elements, cosa que no hauria de ser el cas perquè l'element sigui l'element majoritari. Per tant, l'element candidat no pot ser la majoria i, per tant, escollim l'element present com a candidat i continuem igual fins que s'acabin tots els elements. El candidat final seria el nostre element majoritari. Comprovem mitjançant el segon recorregut per veure si el seu recompte és superior a N/2. Si és cert, ho considerem com l'element majoritari.

Passos per implementar l'algorisme:
Pas 1 - Trobeu un candidat amb la majoria -

• Inicialitzar una variable per dir i, vots = 0, candidat = -1
• Travessa la matriu utilitzant el bucle for
• Si vots = 0, Escull el candidat = arr[i] , fer vots=1 .
• sinó si l'element actual és el mateix que els vots d'increment del candidat
• en cas contrari disminuir els vots.

Pas 2 - Comproveu si el candidat té més de N/2 vots -

• Inicialitzar un recompte variable =0 i augmentar el recompte si és el mateix que el candidat.
• Si el recompte és> N/2, retorneu el candidat.
• sinó torna -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 Per tant, 1 és l'element majoritari.>

C++

quan va sortir la victòria 7

>

>

Java

java llegir csv

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # 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> 
 
 
 
 
    
rebaixa tachada
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
commutador 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.Length / 2)) retornar candidat;  retorn -1;  // L'últim bucle for i el pas de la instrucció if es poden // ometre si es confirma que un element majoritari // està present en una matriu només retorna el candidat // en aquest cas } // Codi del controlador public static void Main(String[ ] args) { int []arr = { 1, 1, 1, 1, 2, 3, 4};  int majoria = findMajority(arr);  Console.Write(' L'element majoritari és : ' + majoria);  } } // Aquest codi és aportat per shivanisinghss2110>>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // 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)) tornar candidat;  retorn -1;  // L'últim bucle for i el pas de la instrucció if es poden // ometre si es confirma que un element majoritari // està present en una matriu només retorna el candidat // en aquest cas } // Codi del controlador var arr = [ 1, 1 , 1, 1, 2, 3, 4 ];  var majoria = findMajority(arr);  document.write(' L'element majoritari és : ' + majority);   // Aquest codi és aportat per shivanisinghss2110.>>>
 
 
 
 
    
 
> 
La cadena de Java està buida
    
  The majority element is : 1>
 
  Complexitat temporal: O(n) (Per a dues passades sobre la matriu) 
  Complexitat espacial: O(1)