Algoritmo para remover elementos duplicados de um array ordenado

Os arrays são estruturas de dados amplamente conhecidas por programadores de diversas linguagens. Inclusive, em boa parte das ocasiões, o array é a primeira estrutura de dados que um desenvolvedor aprende, dada a sua simplicidade.

Entretanto, por mais que os arrays sejam estruturas fáceis de se utilizar, existem muitos problemas que podem ser solucionados com a sua aplicação.

Um desafio que costuma ser frequente em entrevistas de emprego e até mesmo em plataformas que testam o know-how dos programadores, consiste na remoção de todos os elementos duplicados de um array que esteja previamente ordenado.

Assim como outros exercícios do âmbito de algoritmos e estruturas de dados, este problema pode ser resolvido de muitas maneiras. Neste artigo, analisaremos duas soluções possíveis. A primeira delas exigirá espaço extra de memória, enquanto a segunda será mais otimizada, consumindo um espaço constante de memória.

Entendendo o problema

Antes de nos aprofundarmos na resolução, devemos compreender um pouco melhor os cenários existentes do desafio, a partir de alguns exemplos.

Considere um array de seis elementos, composto pelos números 1, 3, 4, 4, 5 e 6. Se passarmos esse vetor como argumento da função que remove as ocorrências repetidas, o valor de retorno do método seria uma estrutura com cinco itens: 1, 3, 4, 5 e 6.

Nas situações em que o array fornecido para a função não apresentasse duplicatas, a saída da rotina seria o próprio vetor original. Ou seja, imagine agora uma estrutura de cinco elementos, formada pelos números 5, 7, 9, 10 e 15. Nesse caso, o procedimento de remoção dos itens repetidos retornaria exatamente os elementos 5, 7, 9, 10 e 15.

Usando espaço auxiliar de memória para solucionar o problema

Conforme mencionado no início da publicação, uma das alternativas que resolvem este problema implica no uso do espaço auxiliar de memória. Quando um programa detém a característica em questão, certos fatores podem ser observados para classificá-lo de tal modo.

O primeiro fator é a recursividade. A partir do momento que uma função se referencia, as suas chamadas subsequentes são armazenadas na pilha de execução, que geralmente variam em termos do input. Portanto, a aplicação acaba ocupando um espaço extra na memória para realizar todos os cálculos necessários.

Já o segundo fator, que é o mais comum e se encaixa com o desafio sendo investigado, envolve a declaração de alguma estrutura de dados no corpo da rotina. Obrigatoriamente, essa estrutura deve ter a sua capacidade de armazenamento atrelada ao input da função.

Examinando o código acima, a primeira linha do método faz com que o espaço auxiliar de memória deixe de ser constante. Isso porque o array denominado temp está sendo instanciado de acordo com a quantidade de elementos n passada para a função. Em outras palavras, sempre haverá uma cópia do vetor original quando a rotina for executada.

Ademais, a lógica por trás da função demonstra ser bastante simples. A fim de facilitar ainda mais o entendimento do algoritmo, uma descrição em etapas do código-fonte está disponível logo abaixo.

1. O array temp é declarado para armazenar a mesma quantidade de itens n do vetor recebido como argumento do método.
2. A primeira posição do array arr é copiada para a primeira posição do array temp.
3. Uma variável contadora identificada como res é atribuída com o valor inicial de um. Ela mantém o controle de quantos números únicos existem no vetor.
4. Iniciando da posição 1, o array arr é percorrido até o seu último elemento. A cada iteração, há a checagem de uma instrução condicional. Se o item atual no vetor arr for diferente do item anterior no vetor temp, o número vigente de arr acaba por ser copiado para o array temp, e a variável res tem o seu valor incrementado.
5. Iniciando da posição 0, o array temp é percorrido até o índice res. Isto é, apenas os elementos não duplicados são movidos para arr.
6. O método retorna a quantidade de itens exclusivos.

Usando espaço constante de memória para solucionar o problema

A solução anterior cumpre o seu propósito, removendo qualquer duplicidade localizada em arrays ordenados. Contudo, há um jeito de descomplicar o algoritmo e torná-lo mais eficiente. 

Ao invés de ocupar espaço extra de memória, a função pode se beneficiar do uso de espaço constante. Isso significa que independente do input, o procedimento utilizará o mesmo espaço de memória.

Perceba que o código fonte assemelha-se com o seu precedente. Na verdade, ele é idêntico, exceto pelos trechos em que o array auxiliar temp acaba por ser declarado e posteriormente copiado para o array arr.

1. Uma variável contadora identificada como res é atribuída com o valor inicial de um. Ela mantém o controle de quantos números únicos existem no vetor.
2. Iniciando da posição 1, o array arr é percorrido até o seu último elemento. A cada iteração, há a checagem de uma instrução condicional. Se o item atual no vetor arr for diferente do seu item anterior, o número vigente de arr no índice i acaba por ser copiado para o índice res, que na sequência tem o seu valor incrementado.
3. O método retorna a quantidade de itens exclusivos.

Analisando a complexidade das soluções

Em contextos nos quais um problema detém mais de uma solução, habitua-se comparar os diferentes algoritmos para determinar o que possui maior eficiência. Duas variáveis principais são consideradas nesse tipo de análise: a complexidade de tempo e a complexidade de memória, esta última apelidada também de espaço auxiliar de memória.

De maneira óbvia, a complexidade de tempo mede a ordem de crescimento de tempo de uma função, tendo em vista o tamanho do input. Esse diagnóstico não depende da máquina que executa o algoritmo, muito menos da linguagem de programação utilizada ou de qualquer outro fator externo.

Por outro lado, a complexidade de memória inspeciona o espaço extra ou espaço temporário usado por um algoritmo. Em outros termos, verifica o espaço total ocupado com relação ao tamanho do input. Logo, esta complexidade é um conceito paralelo à complexidade de tempo.

No que diz respeito à complexidade de tempo das soluções demonstradas nesta postagem, ambas dispõem de uma complexidade linear. Portanto, o tempo de execução dos métodos aumenta linearmente, consoante a quantidade de elementos existentes no vetor arr. Isso acontece porque as duas funções rodam pelo menos um loop for, que percorre os n itens do array.

Levando em conta que a complexidade de tempo dos algoritmos é a mesma, a complexidade de memória fica responsável por nos dizer qual solução se sobressai. Seja dito de passagem, as seções anteriores da publicação já nos adiantaram quanto a isso.

O primeiro algoritmo possui uma complexidade de memória linear, pois declara em seu corpo outra estrutura de dados que muda de tamanho proporcionalmente ao input. Todavia, o segundo algoritmo acaba ganhando a disputa, uma vez que a sua complexidade de memória é constante.

Toda a análise de complexidade feita até então pode ser comprovada e visualizada com o apoio da ferramenta BenchmarkDotNet, que gera indicadores no que tange à performance dos algoritmos.

Método	Input	Média de tempo	Espaço alocado
MétodoUsandoEspaçoConstante	InputInt32[11]	Média de tempo18.602 ns	Espaço alocado-
MétodoUsandoEspaçoExtra	InputInt32[11]	Média de tempo34.676 ns	Espaço alocado72 B
MétodoUsandoEspaçoConstante	InputInt32[17]	Média de tempo30.483 ns	Espaço alocado-
MétodoUsandoEspaçoExtra	InputInt32[17]	Média de tempo49.932 ns	Espaço alocado96 B
MétodoUsandoEspaçoConstante	InputInt32[5]	Média de tempo8.442 ns	Espaço alocado-
MétodoUsandoEspaçoExtra	InputInt32[5]	Média de tempo18.404 ns	Espaço alocado48 B

Nas três simulações realizadas, a função UsandoEspaçoConstante não precisou alocar qualquer recurso de memória adicional na sua execução. Além disso, quando comparado ao método UsandoEspaçoExtra, a média de tempo para remover os itens duplicados foi relativamente menor. Ainda que do ponto de vista da análise de algoritmos os dois procedimentos detenham a mesma complexidade de tempo, a rotina UsandoEspaçoExtra executa um loop extra, o que acaba influenciando no resultado prático.

O código-fonte completo dos algoritmos e os detalhes extras a respeito da performance de cada um deles estão disponíveis no meu repositório do Github.