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

0 Flares Facebook 0 0 Flares ×

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:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: