Elemento majoritário de um vetor

Estou com dificuldade para entender por que um algoritmo funciona, e quero entender
suficientemente bem para explicá-lo. Também não consegui resolver o problema
por indução, mas sei que existe alguma solução por esse caminho. Queria
saber se alguém pode ajudar com alguma das duas coisas.

Problema: Seja V um vetor com \(n\) inteiros. Um inteiro é um elemento majoritário
em V se ocorre (estritamente) mais que \(n/2\) vezes vezes em V. Fazer um
algoritmo para determinar se existe e, caso exista, qual é o elemento majoritário.

Por exemplo: Se V = [1, 2, 3] ou V = [1, 1, 2, 3], não existe elemento
majoritário. Mas 1 é o elemento majoritário de [1, 2, 1] e [1, 2, 1, 1].

Algumas idéias para resolver são (minhas dúvidas não são com elas):

• Faz um laço duplo: para cada i, conta quantas vezes V[i] aparece (\(O(n^2)\)).
• Ordena o vetor e depois conta quantas vezes V[n/2] aparece (\(O(n\log n)\)).
• Encontra a mediana do vetor (algoritmo não trivial, mas é \(O(n)\) no tempo e acho que na memória extra também) e verifica se é elemento majoritário.
• Usa uma hash para fazer contar quantas vezes cada número aparece e depois olha na hash qual o número que apareceu mais vezes. O resultado é bom em tempo (\(O(n)\)) mas demanda memória extra (\(O(m)\), onde \(m\) é número de valores diferentes do vetor, o que é \(O(n)\)).

E tem a solução que eu encontrei na internet e não estou entendendo muito
bem porque funciona. Ela é \(O(n)\) no tempo e \(O(1)\) na memória. A idéia
é fazer em dois passos (ambos \(O(n)\)):

1. Encontrar um possível elemento majoritário
2. Verificar se ele é um elemento majoritário

O passo 2 é simples, basta percorrer o vetor contando quantas vezes ele apareceu.
Por cima, a idéia para a parte 1 é: mantém um contador e um valor provável
e passa pelo vetor (aka. faz um for). A cada valor, se ele for igual ao valor
provável, incrementa o contador, se não, decrementa o contador. Se o contador
for zerado, o valor atual se torna o novo valor provável. No final, o valor
provável será o elemento majoritário se ele existir. Código:

int find_majority(int *v, int n) {
    int count = 1;
    int majority = v[0];
    for (i = 1 ; i < n; i ++) {
        if (v[i] == majority)
            count++;
        else
            count--;
        if (count == 0) {
            majority = v[i];
            count = 1;
        }
    }
    return majority;
}

Além desses algoritmos, aparentemente existem duas soluções por indução
(recursivas), uma tirando um elemento de cada vez do vetor, e outra retirando
dois, mas não consegui concluir nenhuma das duas. Sempre fica faltando alguma
coisa no caso de o resultado do subproblema indicar que não existe elemento
majoritário! Provavelmente está faltando modificar a indução para que ela
dê mais resultados além do elemento majoritário e da quantidade de vezes
que ele aparece.

Resumindo: Queria uma explicação para a parte 1 do algoritmo que eu apresentei
(por que ele funciona?), e uma luz para encontrar alguma solução por indução.
Também aceito outras soluções :)