Remova Duplicatas no Próprio Array

Dado um vetor ordenado, mantenha uma cópia de cada valor sem usar outro vetor. Fazer isso no próprio vetor economiza memória e é uma solicitação clássica em entrevistas. 🧹

Quando o vetor está ordenado, cada duplicata fica imediatamente ao lado de sua cópia. Assim, você só precisa comparar vizinhos, nunca o vetor inteiro.

Use um ponteiro lento, que marca o último valor mantido, e um ponteiro rápido, que percorre adiante procurando algo novo.

Pense em slow como a posição de escrita: tudo que está nessa posição ou antes dela já foi limpo e não contém duplicatas.

O ponteiro fast apenas lê para a frente. Ele avança rapidamente e só sinaliza slow quando encontra um valor que ainda não foi mantido.

Se a[fast] for igual a a[slow], trata-se de uma repetição, então não faça nada além de avançar fast. A duplicata é simplesmente ignorada.

Quando a[fast] for diferente, avance slow e copie o novo valor para essa posição. Isso substitui duplicatas antigas por dados novos e distintos.

Depois da varredura, slow + 1 é a quantidade de valores distintos, todos reunidos no início do vetor.

O que estiver depois do prefixo de valores distintos será apenas sobra irrelevante. O problema se importa apenas com os primeiros elementos slow + 1, portanto deixe o final como está.

Um vetor vazio tem zero valores distintos. Verifique n == 0 antes de começar para não ler além do final.

Esse padrão de ponteiros lento e rápido executa em tempo O(n) e usa O(1) de espaço extra, exatamente o que limites de memória rigorosos exigem.

Você está removendo duplicatas no próprio vetor ordenado com ponteiros lento e rápido.

Em um vetor ordenado, um par de ponteiros lento e rápido remove duplicatas em uma única passagem O(n), sem espaço extra, retornando slow + 1 como a quantidade de valores distintos. 🎉