Algoritmo de votación mayoritaria de Boyer-Moore

El algoritmo de votación de Boyer-Moore 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 ocurrencias. Esto funciona perfectamente bien para encontrar el elemento mayoritario que toma 2 recorridos sobre los elementos dados, lo que funciona en complejidad de tiempo O (N) y complejidad de espacio 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 funciona en el hecho de que si un elemento aparece más de N/2 veces, significa que los elementos restantes que no sean este definitivamente serían menos de N/2. Así que vamos a comprobar el procedimiento del algoritmo.

• Primero, elija un candidato del conjunto dado de elementos si es el mismo que el elemento candidato, aumente los votos. De lo contrario, disminuya los votos si los votos se convierten en 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 cuando se encuentra algún otro elemento que no es igual al elemento candidato. Disminuimos el conteo. En realidad, esto significa que estamos disminuyendo la prioridad de la capacidad ganadora del candidato seleccionado, ya que sabemos que si el candidato es 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 algún elemento diferente al elemento candidato. Cuando los votos se convierten en 0, en realidad significa que hay el mismo número de elementos diferentes, 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, por lo que elegimos el elemento presente 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 cuenta es mayor que N/2. Si es cierto, lo consideramos como el elemento mayoritario.

Pasos para implementar el algoritmo:
Paso 1 – Encontrar un candidato con la mayoría –

• Inicialice una variable, digamos i, votos = 0, candidato = -1 
• Atraviesa la array usando for loop
• Si votos = 0, elija el candidato = arr[i] , haga votos = 1 .
• de lo contrario, si el elemento actual es el mismo que el candidato, se incrementan los votos
• de lo contrario, disminuir los votos.

Paso 2: compruebe si el candidato tiene más de N/2 votos:

• Inicialice una cuenta variable = 0 e incremente la cuenta si es la misma que la candidata.
• Si el conteo es >N/2, devuelva 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
 So 1 is the majority element.

// C++ implementation for the above approach
#include <iostream>
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 < n; 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 < n; i++) {
        if (arr[i] == candidate)
            count++;
    }
 
    if (count > n / 2)
        return candidate;
    return -1;
}
int main()
{
    int arr[] = { 1, 1, 1, 1, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int majority = findMajority(arr, n);
    cout << " The majority element is : " << majority;
    return 0;
}

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 < nums.length; 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 < nums.length; index++) {
      if (nums[index] == candidate)
        count++;
    }
    if (count > (nums.length / 2))
      return candidate;
    return -1;
 
    // The last for loop and the if statement step can
    // be skip if a majority element is confirmed to
    // be present in an array just return candidate
    // in that case
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int arr[] = { 1, 1, 1, 1, 2, 3, 4 };
    int majority = findMajority(arr);
    System.out.println(" The majority element is : "
                       + majority);
  }
}
 
// This code is contribute by Arnav Sharma

# 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 

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 < nums.Length; 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 < nums.Length; index++) {
      if (nums[index] == candidate)
        count++;
    }
    if (count > (nums.Length / 2))
      return candidate;
    return -1;
 
    // The last for loop and the if statement step can
    // be skip if a majority element is confirmed to
    // be present in an array just return candidate
    // in that case
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int []arr = { 1, 1, 1, 1, 2, 3, 4};
    int majority = findMajority(arr);
    Console.Write(" The majority element is : "
                       + majority);
  }
}
 
// This code is contributed by shivanisinghss2110

<script>
// Function to find majority element
function findMajority(nums)
  {
    var count = 0, candidate = -1;
 
    // Finding majority candidate
    for (var index = 0; index < nums.length; 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 < nums.length; index++) {
      if (nums[index] == candidate)
        count++;
    }
    if (count > (nums.length / 2))
      return candidate;
    return -1;
 
    // The last for loop and the if statement step can
    // be skip if a majority element is confirmed to
    // be present in an array just return candidate
    // in that case
  }
 
// Driver code
    var arr = [ 1, 1, 1, 1, 2, 3, 4 ];
    var majority = findMajority(arr);
    document.write(" The majority element is : "
                       + majority);
   
 
// This code is contributed by shivanisinghss2110.
 
</script>

 The majority element is : 1

Complejidad de tiempo: O(n) (Para dos pases sobre la array)
Complejidad de espacio: O(1)