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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // 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