Solução por Lucca Siaudzionis
Vamos dificultar um pouquinho a questão: não necessariamente há um elemento majoritário, neste caso, diga que não há. Resolver este problema é um processo de duas etapas:
- Achar um elemento que seja candidato a ser a resposta.
- Checar caso o elemento encontrado acima é majoritário.
1) Achar um candidato
O algoritmo para esta etapa roda em $$O(n)$$ e é conhecido por Algoritmo de Moore. A ideia básica do algoritmo é cancelar cada ocorrência de um elemento $$e$$ com todos os elementos diferentes de $$e$$ e ir deixando esse número de ocorrências num contador $$c$$ (subtraindo um quando é diferente de $$e$$). Caso o $$c$$ chegue a zero, atualizamos o valor de $$e$$. O nosso último valor de $$e$$ é nosso candidato. Inicializamos $$e$$ para o primeiro elemento do array e $$c$$ para 1.
2) Checar se é majoritário
Ao final, simplesmente percorremos o array e contamos o número de ocorrências do nosso candidato e checamos se é majoritário.
Abaixo, o código para o problema original:
| // | |
| // majority.cpp | |
| // programas2 | |
| // | |
| // Created by Lucca Siaudzionis on 27/03/13. | |
| // Copyright (c) 2013 Luccasiau. All rights reserved. | |
| // | |
| #include <cstdio> | |
| #define MAXN 3000005 | |
| int myv[MAXN]; | |
| int main(){ | |
| int n; | |
| scanf("%d",&n); | |
| for(int i = 1;i<=n;i++) scanf("%d",&myv[i]); | |
| int index = 1; | |
| int count = 1; | |
| for(int i = 2;i<=n;i++){ | |
| if(myv[i] == myv[index]) count++; | |
| else count–; | |
| if(!count){ | |
| index = i; | |
| count = 1; | |
| } | |
| } | |
| printf("%d\n",myv[index]); | |
| return 0; | |
| } |

Comente