Problema da Maioria

Como determinar se algum candidato recebeu mais de 50% dos votos em tempo linear. Esse problema é conhecido como problema da maioria. Formalmente,

Dada uma sequência de n elementos onde cada elemento é um inteiro x $\in$ [1..k] devolva o elemento majoritário, ou seja, o elemento que aparece mais do que $\frac{n}{2}$ ou zero se nenhum elemento é encontrado.

Algoritmo baseado em contagem

int MajorityCount(int v[], int n, int k){
  int c[k];
  int i;
  for(i=0;i<k;i++) c[i] = 0;
  for(i=0;i<n;i++) c[v[i]]++;
  for(i=0;i<k;i++)
    if(c[i] > n/2 ) return i;
  return 0;
}

Complexidade de tempo O(n+k)
Complexidade de espaço extra O(k)

Algoritmo baseado em comparações

Força Bruta

int MajorityBrute(int v[], int n)
{
  int i;
  for(i=0; i< n; i++)
  {
    int count = 1;
    int item = v[i];
    int j;
    for(j=i+1; j <= n; j++)
    {
      if (v[j] == item) count++; }
      if (count > n/2) return item;
    }
    return 0;
}

Complexidade de tempo O($n^2$)
Complexidade de espaço extra O(1)

Divisão e Conquista

int Count(int v[], int lo, int hi, int x){
  int k;
  int cont = 0;
  for(k=lo;k<=hi;k++)
    if(v[k]==x) cont++;
  return cont;
}

int MajorityDivideConquer(int v[], int lo, int hi)
{
  if (lo > hi) return 0; // empty sequence case
  else if (lo == hi) return v[lo]; // one-element sequence case
  else // general case
  {
    int mid = lo + (hi-lo)/2; // integer division
    int x = MajorityDivideConquer(v,lo,mid);
    int y = MajorityDivideConquer(v,mid+1,hi);
    if (x==y) return x; // x and y are both zero or both majority
    if (x > 0) // x is a majority in 1st half
    if ( Count(v,lo, hi,x) > (hi-lo+1)/2 ) return x;
    if (y > 0) // y is a majority in 2nd half
    if ( Count(v,lo, hi,y) > (hi-lo+1)/2 ) return y;
    return 0;
  }
}

Complexidade de tempo


C(n) = C(n/2) + C(n−n/2) + 2n
C(0) = C(1) = 0

Simplificando para C(n)=2C(n/2)+2n


Complexidade de tempo O(n lg n)

Moore’s Voting Algorithm

int MajorityLinearMoore(int v[], int n){
     int maj_index = 0;
     int count = 1;
     int i;
     for (i = 1; i < n; i++ ){
      if (v[maj_index] == v[i]) count++;
      else count--;
      if (count == 0){
        maj_index = i;
        count = 1;
      }
     }
    if( Count(v, 0, n-1, v[maj_index]) > n/2 )
      return v[maj_index];
    else
      return 0;
}

A corretude deste algoritmo é baseado nas seguintes observações:

1. se v[1..n] tem um valor majoritário e se A[n-1] $\neq$ A[n] então A[1..n-2] também tem um valor majoritário. A mesma observação vale para quaisquer dois elementos do vetor: se A[i] $\neq$ A[j] e A tem um valor majoritário então o vetor que se obtém pela eliminação das posições i e j também tem um valor majoritário. Observe que quando o valor count == 0, o algoritmo recomeça. Isso quer dizer que todos os valores anteriores podem ser eliminados.
2. Para qualquer k $\in$ [1..n], se x é majoritário de A[1..n] se somente se x é majoritário em A[1..k-1] ou A[k..n] ou em ambos. 

Complexidade de tempo O(n)

Problema SPOJ
http://www.spoj.com/problems/MAJORITY/
http://www.spoj.com/problems/MAJOR/


Referências:
Majority Element : http://www.geeksforgeeks.org/majority-element/
Minicurso de Análise de Algoritmos http://www.ime.usp.br/~pf/livrinho-AA/