Qual é a melhor maneira de remover duplicatas em uma matriz em Java?

Question

Eu tenho uma matriz de objetos que precisam as duplicatas removidas / filtrados. Eu ia apenas iguais substituição e hachCode sobre os elementos do objeto e, em seguida, colocá-los em um conjunto ... mas eu percebi que eu deveria stackoverflow pelo menos enquete para ver se havia outra maneira, talvez algum método inteligente de alguma outra API?

Answer 1

Eu concordo com a sua abordagem para hashCode() override e equals() e uso algo que implementa Set.

Isso também faz com que seja absolutamente claro para todos os outros desenvolvedores que a característica não-duplicado é necessária.

Outra razão - você começa a escolher uma implementação que atenda às suas necessidades melhor agora:

• HashSet
• TreeSet
• LinkedHashSet

e você não tem que alterar seu código para alterar a implementação no futuro.

Answer 2

Eu encontrei este na web

Aqui estão dois métodos que permitem que você remover duplicatas em um ArrayList. não removeDuplicate não manter a ordem onde, como removeDuplicateWithOrder mantém a ordem com alguma sobrecarga de desempenho.

1. O Método removeDuplicate:

   /** List order not maintained **/
   public static void removeDuplicate(ArrayList arlList)
   {
    HashSet h = new HashSet(arlList);
    arlList.clear();
    arlList.addAll(h);
   }
   

2. O Método removeDuplicateWithOrder:

   /** List order maintained **/
   public static void removeDuplicateWithOrder(ArrayList arlList)
   {
      Set set = new HashSet();
      List newList = new ArrayList();
      for (Iterator iter = arlList.iterator(); iter.hasNext();) {
         Object element = iter.next();
         if (set.add(element))
            newList.add(element);
      }
      arlList.clear();
      arlList.addAll(newList);
   }
   

Answer 3

Substituir equals e hashCode e criando um set foi o meu primeiro pensamento também. É uma boa prática para ter alguma versão substituída destes métodos de qualquer maneira em sua hierarquia de herança.

I pensar que se você usar um LinkedHashSet você vai mesmo preservar a ordem dos elementos únicos ...

Answer 4

Basicamente, você quer uma implementação LinkedHashSet<T> que suporta a interface List<T> para acesso aleatório. Assim, este é o que você precisa:

public class LinkedHashSetList<T> extends LinkedHashSet<T> implements List<T> {

// Implementations for List<T> methods here ...

}

A implementação dos métodos List<T> poderia acessar e manipular o LinkedHashSet<T> subjacente. O truque é fazer com que este se comportam classe corretamente quando se tenta adicionar duplicatas através dos métodos List<T> ADD (jogando uma exceção ou re-adicionar o item em um índice diferente seria opções: o que você pode escolher uma das ou fazer configurável por usuários da classe).

Answer 5

Use um distinctList Lista de elemento recorde no primeiro tropeço iterator tempo para ele, retorna o distinctList como lista removido todas as duplicatas

 private List removeDups(List list) {
        Set tempSet = new HashSet();
        List distinctList = new ArrayList();
        for(Iterator  it = list.iterator(); it.hasNext();) {
            Object next = it.next();
            if(tempSet.add(next)) {
                distinctList.add(next);
            } 
        }
        return distinctList;
   } 

Answer 6

Eu gostaria de reiterar o ponto feito por Jason nos comentários:

Por que lugar se naquele ponto em tudo?

Por que usar uma matriz para uma estrutura de dados que não devem segurar duplicatas em tudo?

Use um Set ou um SortedSet (quando os elementos têm uma ordem natural também) em todos os momentos para prender os elementos. Se você precisa manter a ordem de inserção, então você pode usar o LinkedHashSet como tem sido apontado.

Ter de pós-processo de alguma estrutura de dados é muitas vezes uma dica que você deveria ter escolhido um diferente para começar.

Answer 7

É claro que o post original levanta a questão: "Como você conseguiu esse array (que pode conter entradas duplicadas), em primeiro lugar?"

Você precisa do array (com duplicatas) para outros fins, ou você pode simplesmente usar um conjunto desde o início?

Como alternativa, se você precisa saber o número de ocorrências de cada valor, você poderia usar um Map<CustomObject, Integer> para rastrear as contagens. Além disso, o definição das classes Multimap Google Collections podem ser de uso.

Answer 8

A Set é definitivamente a melhor aposta. A única forma de remover as coisas de uma matriz (sem criar um novo) é a null-los para fora, e depois você acaba com um monte de nulos-cheques mais tarde.

Answer 9

Falando de um padrão de programação geral que você poderia sempre o dobro enumerar as coleções então a comparar a origem e destino.

E se a sua enumeração interna começa sempre uma entrada após a fonte, é bastante eficiente (código pseudo a seguir)

foreach ( array as source )
{
    // keep track where we are in the array
    place++;
    // loop the array starting at the entry AFTER the current one we are comparing to
    for ( i=place+1; i < max(array); i++ )
    {
        if ( source === array[place] )
        {
            destroy(array[i]);
        }
    }
}

Você poderia possivelmente adicionar uma quebra; declaração após a destruir, mas então você só descobrir o primeiro duplicado, mas se isso é tudo que você nunca vai ter, então seria uma pequena otimização agradável.