sexta-feira, 21 de março de 2014

Dica rápida: como saber se há itens duplicados em um List no Java?

Olá, pessoal!

A pergunta pode parecer muito simples, mas acredite, ela pode ter soluções e desdobramentos interessantes!

Estava eu desenvolvendo normalmente, e apareceu um pequeno problema em que eu precisaria evitar que elementos duplicados estivessem em um List (ArrayList). Quando encontro problemas simples que podem ter diferentes soluções, eu costumo fazer uma pesquisa no Google, no qual costumo sempre parar no StackOverFlow, para saber o quão criativo e eficiente podem ser as soluções de outros desenvolvedores. Sempre aprendo algo novo e, o melhor, normalmente não é com a solução mais votada!

Inclusive, se um dia me acompanharem programando, vão se deparar comigo digitando no Google por soluções para questões tão básicas como esta... =P

Surpreendido após o resultado da minha pesquisa, fiz a pergunta a alguns de meus colegas e pedi para eles dizerem a primeira solução eficiente que vierem à cabeça de cada um. Apareceram várias soluções:

  1. Ordenar a lista e percorrê-la, identificando se o próximo elemento da lista era igual ao atual.
  2. Percorrer a List, adicionando cada elemento em uma nova lista, verificando se o elemento que está sendo adicionado já não existe nesta nova lista.
  3. Transformar a List em um Set, para depois voltar para List .

Acredito que tenham ocorrido mais algumas ainda!

Posteriormente, fiz outra pergunta:

Se eu quiser não removê-los, mas apenas saber se existem elementos duplicados?


Outras soluções apareceram e um deles já indicou uma das formas mais elegantes de o fazê-lo, que é copiar uma List para Set e verificar se o tamanho da List original difere do tamanho do Set.


List<Integer> list = ...;
Set<Integer> set = new HashSet<Integer>(list);

if(set.size() < list.size()){
    /* There are duplicates */
}

Assim, fiz a última pergunta:

E se eu quiser saber qual elemento é o duplicado?


A solução 2 parecia ser a mais correta agora. Mas, o interessante é a forma como podemos implementá-la... Depois que mostrei esta solução para os meus colegas, foi muito interessante ver a reação deles. Por mais que você entenda de coleções em Java, poucos pensariam nisto:


public static <T> boolean hasDuplicate(Iterable<T> all) {
    Set<T> set = new HashSet<T>();
    // Set#add returns false if the set does not change, which
    // indicates that a duplicate element has been added.
    for (T each: all) if (!set.add(each)) return true;
    return false;
}

Eu sei que é simples, mas não é legal? =)

Querem uma outra dica? Façam uma pesquisa sobre remover elementos duplicados de um List preservando a ordem dos elementos (lembrando que qualquer transformação de List para HashSet altera a ordenação).