El Votación de Boyer-Moore El algoritmo es uno de los algoritmos óptimos populares que se utiliza para encontrar el elemento mayoritario entre los elementos dados que tienen más de N/ 2 apariciones. Esto funciona perfectamente bien para encontrar el elemento mayoritario que requiere 2 recorridos sobre los elementos dados, lo que funciona en complejidad temporal O(N) y complejidad espacial O(1).
Veamos el algoritmo y la intuición detrás de su funcionamiento, tomando un ejemplo:
Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1> Este algoritmo se basa en el hecho de que si un elemento aparece más de N/2 veces, significa que los elementos restantes además de este definitivamente serían menores que N/2. Entonces, verifiquemos el procedimiento del algoritmo.
- Primero, elija un candidato del conjunto de elementos dado, si es el mismo que el elemento candidato, aumente los votos. De lo contrario, disminuya los votos si los votos llegan a 0, seleccione otro elemento nuevo como nuevo candidato.
Intuición detrás del trabajo:
Cuando los elementos son los mismos que el elemento candidato, los votos se incrementan, mientras que cuando se encuentra algún otro elemento (no igual al elemento candidato), disminuimos el recuento. En realidad, esto significa que estamos disminuyendo la prioridad de capacidad ganadora del candidato seleccionado, ya que sabemos que si el candidato tiene mayoría ocurre más de N/2 veces y los elementos restantes son menos de N/2. Seguimos disminuyendo los votos ya que encontramos algunos elementos diferentes al elemento candidato. Cuando los votos se vuelven 0, esto en realidad significa que hay el mismo número de votos para diferentes elementos, lo que no debería ser el caso para que el elemento sea el elemento mayoritario. Entonces, el elemento candidato no puede ser la mayoría y, por lo tanto, elegimos el elemento actual como candidato y continuamos igual hasta que todos los elementos estén terminados. El candidato final sería nuestro elemento mayoritario. Verificamos usando el segundo recorrido para ver si su recuento es mayor que N/2. Si es cierto, lo consideramos como el elemento mayoritario.
eliminando de la lista de matrices
Pasos para implementar el algoritmo:
Paso 1 - Encuentre un candidato con la mayoría –
- Inicializar una variable digamos i, votos = 0, candidato =-1
- Atraviesa la matriz usando el bucle for
- Si votos = 0, elegir el candidato = llegada[i] , hacer votos=1 .
- de lo contrario, si el elemento actual es el mismo que el incremento de votos del candidato
- de lo contrario, disminuirá los votos.
Paso 2 - Compruebe si el candidato tiene más de N/2 votos –
- Inicialice un recuento de variables = 0 e incremente el recuento si es el mismo que el candidato.
- Si el recuento es>N/2, devuelve el candidato.
- de lo contrario, devuelve -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 Entonces 1 es el elemento mayoritario.>
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) candidato de retorno; devolver -1; } int principal() { int arreglo[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = tamaño de (arr) / tamaño de (arr [0]); int mayoría = findMajority(arr, n); corte<< ' The majority element is : ' << majority; return 0; }> |
>
>
Java
inttostr 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)) candidato de retorno; devolver -1; // El último bucle for y el paso de la instrucción if se pueden // omitir si se confirma que un elemento mayoritario // está presente en una matriz, solo devuelve el candidato // en ese caso } // Código del controlador public static void main(String[ ] argumentos) { int arreglo[] = { 1, 1, 1, 1, 2, 3, 4 }; int mayoría = findMajority(arr); System.out.println(' El elemento mayoritario es: ' + mayoría); } } // Este código es una contribución de 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> |
algoritmo de clasificación por inserción
>
>
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)) candidato de retorno; devolver -1; // El último bucle for y el paso de la instrucción if se pueden // omitir si se confirma que un elemento mayoritario // está presente en una matriz, solo devuelve el candidato // en ese caso } // Código del controlador public static void Main(String[ ] argumentos) { int []arr = { 1, 1, 1, 1, 2, 3, 4}; int mayoría = findMajority(arr); Console.Write(' El elemento mayoritario es: ' + mayoría); } } // Este código es aportado por shivanisinghss2110> |
aplicaciones de computación en la nube
>
>
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)) candidato de retorno; devolver -1; // El último bucle for y el paso de la declaración if se pueden // omitir si se confirma que un elemento mayoritario // está presente en una matriz, simplemente devuelva el candidato // en ese caso } // Código del controlador var arr = [ 1, 1 , 1, 1, 2, 3, 4 ]; var mayoría = findMajority(arr); document.write(' El elemento mayoritario es: ' + mayoría); // Este código es una contribución de shivanisinghss2110.> |
>
emitir cadena como int
>Producción
The majority element is : 1>
Complejidad del tiempo: O(n) (Para dos pasadas sobre la matriz)
Complejidad espacial: O(1)