TOP 25 ALGORITMOS | Boyer Moore Majority Voting (BMMV)

O algoritmo de votação Boyer-Moore é um dos algoritmos ótimos populares que é usado para encontrar o elemento majoritário entre os elementos dados que têm mais de N/2 ocorrências. Isso funciona perfeitamente bem para encontrar o elemento majoritário que leva 2 travessias sobre os elementos dados, o que funciona em complexidade de tempo O(N) e complexidade de espaço O(1).

📁 | Resumo

🤖 | Código

.
function findMajority(nums){
  var count = 0, candidate = -1;

  // Encontrando candidato majoritário
  for (var index = 0; index < nums.length; index++) {
    if (count == 0) {
      candidate = nums[index];
      count = 1;
    } else {
      if (nums[index] == candidate)
        count++;
      else
        count--;
    }
  }

  // Verificando se o candidato majoritário ocorre mais de n/2 vezes
  count = 0;
  for (var index = 0; index < nums.length; index++) {
    if (nums[index] == candidate)
      count++;
  }
  if (count > (nums.length / 2))
    return candidate;
  return -1;

  // O último loop for e a etapa da instrução if podem ser 
  // ignorados se um elemento majoritário for confirmado como 
  // presente em uma matriz, basta retornar o candidato nesse caso
}
.

🕰️ | Complexidade de Tempo

A complexidade de tempo é O(n), com duas iterações consecutivas, mas ainda linear.

📦 | Complexidade de Espaço

A complexidade de espaço é constante, ou seja, O(1).

✔️ | Vantagens

✦ Eficiente;

✦ Uso mínimo de espaço;

✦ Implementação simples com lógica direta;

✦ Aplicabilidade no fluxo de dados contínuos;

❌ | Desvantagens

✦ Sensibilidade a dados extremos;

✦ Necessidade de validação posterior;

✦ Limitação a um único majority_element;

✦ Estrito para encontrar maiorias simples (>50%);