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:- 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.
- 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/
