Java: Detectar duplicatas no ArrayList?

Como eu poderia ir sobre a detecção (retornando verdadeiro / falso) se um ArrayList contém mais do que um do mesmo elemento em Java?

Muito obrigado, Terry

Editar Esqueci de mencionar que não estou querendo comparar “Blocks” uns com os outros, mas com seus valores inteiros. Cada “bloco” tem um int e é isso que os torna diferentes. Eu acho o int de um determinado bloco, chamando um método chamado “getNum” (por exemplo, table1 [0] [2] .getNum ();

   

Mais simples: despeje toda a coleção em um Set (usando o construtor Set (Collection) ou Set.addAll), então veja se o Set tem o mesmo tamanho que o ArrayList.

List list = ...; Set set = new HashSet(list); if(set.size() < list.size()){ /* There are duplicates */ } 

Update: Se eu estou entendendo sua pergunta corretamente, você tem uma matriz 2d de Block, como em

Tabela de blocos [] [];

e você deseja detectar se alguma linha deles tem duplicatas?

Nesse caso, eu poderia fazer o seguinte, assumindo que o Block implementa "equals" e "hashCode" corretamente:

 for (Block[] row : table) { Set set = new HashSet(); for (Block cell : row) { set.add(cell); } if (set.size() < 6) { //has duplicate } } 

Eu não tenho 100% de certeza disso para syntax, então pode ser mais seguro escrevê-lo como

 for (int i = 0; i < 6; i++) { Set set = new HashSet(); for (int j = 0; j < 6; j++) set.add(table[i][j]); 

...

Código aprimorado, usando o valor de retorno de Set#add vez de comparar o tamanho da lista e definir.

 public static  boolean hasDuplicate(Iterable all) { Set set = new HashSet(); // 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; } 

Se você está procurando evitar duplicatas, então você deve apenas cortar o processo do meio de detectar duplicatas e usar um conjunto .

Código aprimorado para retornar os elementos duplicados

  • Pode encontrar duplicatas em uma coleção
  • devolve o conjunto de duplicados
  • Elementos Únicos podem ser obtidos no Conjunto

 public static  List getDuplicate(Collection list) { final List duplicatedObjects = new ArrayList(); Set set = new HashSet() { @Override public boolean add(T e) { if (contains(e)) { duplicatedObjects.add(e); } return super.add(e); } }; for (T t : list) { set.add(t); } return duplicatedObjects; } public static  boolean hasDuplicate(Collection list) { if (getDuplicate(list).isEmpty()) return false; return true; } 

Se seus elementos são de alguma forma Comparáveis ​​(o fato de que o pedido tem algum significado real é indiferente – ele só precisa ser consistente com sua definição de igualdade), a solução de remoção duplicada mais rápida irá ordenar a lista (0 (n log) n))) então para fazer um único passo e procurar por elementos repetidos (isto é, elementos iguais que se seguem) (isto é O (n)).

A complexidade geral será O (n log (n)), que é aproximadamente o mesmo que você obteria com um Set (n vezes long (n)), mas com uma constante muito menor. Isso ocorre porque a constante em ordenação / desduplicação resulta do custo de comparar elementos, enquanto o custo do conjunto é mais provável de resultar de um cálculo de hash, mais uma (possivelmente várias) comparações de hash. Se você estiver usando uma implementação de conjunto baseada em hash, isto é, porque uma tree baseada lhe dará um O (n log² (n)), que é ainda pior.

Pelo que entendi, no entanto, você não precisa remover duplicatas, mas apenas testar sua existência. Portanto, você deve codificar manualmente um algoritmo de mesclagem ou de sorting de heap em sua matriz, que simplesmente retorna true (ou seja, “há um dup”) se seu comparador retornar 0 e concluir a sorting e passar o teste de matriz classificada para repetições . Em uma sorting de mesclagem ou heap, de fato, quando a sorting for concluída, você terá comparado cada par duplicado, a menos que ambos os elementos já estejam em suas posições finais (o que é improvável). Assim, um algoritmo de ordenação ajustado deve produzir uma grande melhoria de desempenho (eu teria que provar isso, mas eu acho que o algoritmo ajustado deve estar no O (log (n)) em dados uniformemente randoms)

Eu precisava fazer uma operação semelhante para um Stream , mas não consegui encontrar um bom exemplo. Aqui está o que eu inventei.

 public static  boolean areUnique(final Stream stream) { final Set seen = new HashSet<>(); return stream.allMatch(seen::add); } 

Isso tem a vantagem do curto-circuito quando as duplicatas são encontradas mais cedo, em vez de ter que processar todo o stream e não é muito mais complicado do que apenas colocar tudo em um Set e verificar o tamanho. Então, este caso seria aproximadamente:

 List list = ... boolean allDistinct = areUnique(list.stream()); 

Basta colocar: 1) certifique-se de todos os itens são comparáveis ​​2) ordenar a matriz 2) iterar sobre a matriz e encontrar duplicatas

Para saber os duplicados em uma lista, use o seguinte código: Ele fornecerá o conjunto que contém duplicatas.

  public Set< ?> findDuplicatesInList(List< ?> beanList) { System.out.println("findDuplicatesInList::"+beanList); Set duplicateRowSet=null; duplicateRowSet=new LinkedHashSet(); for(int i=0;i 
  String tempVal = null; for (int i = 0; i < l.size(); i++) { tempVal = l.get(i); //take the ith object out of list while (l.contains(tempVal)) { l.remove(tempVal); //remove all matching entries } l.add(tempVal); //at last add one entry } 

Nota: isso terá um grande impacto no desempenho, já que os itens são removidos do início da lista. Para resolver isso, temos duas opções. 1) iterar na ordem inversa e remover elementos. 2) Use LinkedList em vez de ArrayList. Devido a perguntas tendenciosas feitas em entrevistas para remover duplicatas da Lista sem usar qualquer outra coleção, o exemplo acima é a resposta. No mundo real, porém, se eu tiver que conseguir isso, vou colocar elementos de List para Set, simples!

 /** * Method to detect presence of duplicates in a generic list. * Depends on the equals method of the concrete type. make sure to override it as required. */ public static  boolean hasDuplicates(List list){ int count = list.size(); T t1,t2; for(int i=0;i 

Um exemplo de uma class concreta que substituiu equals() :

 public class Reminder{ private long id; private int hour; private int minute; public Reminder(long id, int hour, int minute){ this.id = id; this.hour = hour; this.minute = minute; } @Override public boolean equals(Object other){ if(other == null) return false; if(this.getClass() != other.getClass()) return false; Reminder otherReminder = (Reminder) other; if(this.hour != otherReminder.hour) return false; if(this.minute != otherReminder.minute) return false; return true; } } 
 import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class FindDuplicateInArrayList { public static void main(String[] args) { Set uniqueSet = new HashSet(); List dupesList = new ArrayList(); for (String a : args) { if (uniqueSet.contains(a)) dupesList.add(a); else uniqueSet.add(a); } System.out.println(uniqueSet.size() + " distinct words: " + uniqueSet); System.out.println(dupesList.size() + " dupesList words: " + dupesList); } } 
  ArrayList withDuplicates = new ArrayList<>(); withDuplicates.add("1"); withDuplicates.add("2"); withDuplicates.add("1"); withDuplicates.add("3"); HashSet set = new HashSet<>(withDuplicates); ArrayList withoutDupicates = new ArrayList<>(set); ArrayList duplicates = new ArrayList(); Iterator dupIter = withDuplicates.iterator(); while(dupIter.hasNext()) { String dupWord = dupIter.next(); if(withDuplicates.contains(dupWord)) { duplicates.add(dupWord); }else{ withoutDupicates.add(dupWord); } } System.out.println(duplicates); System.out.println(withoutDupicates); 

A melhor maneira de lidar com esse problema é usar um HashSet :

 ArrayList listGroupCode = new ArrayList<>(); listGroupCode.add("A"); listGroupCode.add("A"); listGroupCode.add("B"); listGroupCode.add("C"); HashSet set = new HashSet<>(listGroupCode); ArrayList result = new ArrayList<>(set); 

Basta imprimir o resultado arraylist e ver o resultado sem duplicatas 🙂