Solução Colônia de Formigas – Semana 2

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:

1. Achar um elemento que seja candidato a ser a resposta.
2. 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:

https://gist.github.com/luccasiau/efe113996bf7683ed526