Java: Detectar duplicatas em ArrayList?

Como posso detectar (retornando verdadeiro / falso) se um ArrayList contém mais de um elemento do mesmo em Java?

Muito obrigado, terry

Editar Esqueci de mencionar que não estou procurando comparar "Blocos" entre si, mas seus valores inteiros. Cada "bloco" tem um int e é isso que os torna diferentes. Eu encontro o int de um bloco específico 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) e veja se o Set tem o mesmo tamanho de ArrayList.

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

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

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

Tabela de blocos [] [];

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

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

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

Não tenho 100% de certeza quanto à sintaxe, então pode ser mais seguro escrevê-la como

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

Set.addretorna um booleano falso se o item que está sendo adicionado já estiver no conjunto, então você pode até mesmo causar um curto-circuito e empatar em qualquer adição que retorne falsese tudo o que você deseja saber é se há alguma duplicata.

Código aprimorado, usando o valor de retorno de em Set#addvez de comparar o tamanho da lista e do conjunto.

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;
}

Se você está procurando evitar duplicatas, então você deve apenas cortar o processo intermediário de detecção de duplicatas e usar um Conjunto .

Código aprimorado para retornar os elementos duplicados

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

public static <T> List getDuplicate(Collection<T> list) {

    final List<T> duplicatedObjects = new ArrayList<T>();
    Set<T> set = new HashSet<T>() {
    @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 <T> boolean hasDuplicate(Collection<T> list) {
    if (getDuplicate(list).isEmpty())
        return false;
    return true;
}

Se seus elementos forem de alguma forma comparáveis ​​(o fato de a ordem ter qualquer significado real é indiferente - ela só precisa ser consistente com sua definição de igualdade), a solução de remoção de duplicatas mais rápida irá classificar a lista (0 (n log ( n))) então fazer uma única passagem e procurar repetidas elementos (ou seja, elementos iguais que se sucedem) (isto é O (n)).

A complexidade geral será O (n log (n)), que é aproximadamente a mesma que você obteria com um Conjunto (n vezes longo (n)), mas com uma constante muito menor. Isso ocorre porque a constante na classificação / desduplicação resulta do custo de comparar elementos, enquanto o custo do conjunto provavelmente resultará de um cálculo de hash, mais uma (possivelmente várias) comparações de hash. Se você estiver usando uma implementação de Set baseada em hash, isto é, porque uma baseada em Árvore vai 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 classificação de pilha em sua matriz, que simplesmente sai retornando verdadeiro (ou seja, "há um dup") se seu comparador retornar 0, e de outra forma completar a classificação e percorrer o teste de matriz classificada para repetições . Em uma mesclagem ou classificação de heap, de fato, quando a classificação for concluída, você terá comparado todos os pares duplicados, a menos que ambos os elementos já estivessem em suas posições finais (o que é improvável). Assim, um algoritmo de classificação ajustado deve produzir uma grande melhoria de desempenho (eu teria que provar isso, mas acho que o algoritmo ajustado deve estar no O (log (n)) em dados uniformemente aleatórios)

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

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

Isso tem a vantagem de causar um curto-circuito quando duplicatas são encontradas no início, em vez de ter que processar todo o fluxo e não é muito mais complicado do que apenas colocar tudo em a Sete verificar o tamanho. Portanto, este caso seria aproximadamente:

List<T> list = ...
boolean allDistinct = areUnique(list.stream());

Com o Java 8+, você pode usar a API Stream:

boolean areAllDistinct(List<Block> blocksList) {
    return blocksList.stream().map(Block::getNum).distinct().count() == blockList.size();
}

Simplificando: 1) certifique-se de que todos os itens são comparáveis ​​2) classifique o array 2) itere sobre o array e encontre duplicatas

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

 public Set<?> findDuplicatesInList(List<?> beanList) {
    System.out.println("findDuplicatesInList::"+beanList);
    Set<Object> duplicateRowSet=null;
    duplicateRowSet=new LinkedHashSet<Object>();
            for(int i=0;i<beanList.size();i++){
                Object superString=beanList.get(i);
                System.out.println("findDuplicatesInList::superString::"+superString);
                for(int j=0;j<beanList.size();j++){
                    if(i!=j){
                         Object subString=beanList.get(j);
                         System.out.println("findDuplicatesInList::subString::"+subString);
                         if(superString.equals(subString)){
                             duplicateRowSet.add(beanList.get(j));
                         }
                    }
                }
            }
            System.out.println("findDuplicatesInList::duplicationSet::"+duplicateRowSet);
        return duplicateRowSet;
  }

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

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

Basta imprimir a lista de resultados e ver o resultado sem duplicatas :)

Se você deseja o conjunto de valores duplicados:

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<String> uniqueSet = new HashSet<String>();
        List<String> dupesList = new ArrayList<String>();
        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);
    }
}

E provavelmente também pense em cortar valores ou usar letras minúsculas ... dependendo do seu caso.

    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, pois 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. Porém, no mundo real, se eu tiver que conseguir isso, colocarei elementos de List to 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 <T> boolean hasDuplicates(List<T> list){
        int count = list.size();
        T t1,t2;

        for(int i=0;i<count;i++){
            t1 = list.get(i);
            for(int j=i+1;j<count;j++){
                t2 = list.get(j);
                if(t2.equals(t1)){
                    return true;
                }
            }
        }
        return false;
    }

Um exemplo de uma classe concreta que foi substituída 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;
    }
}

    ArrayList<String> withDuplicates = new ArrayList<>();
    withDuplicates.add("1");
    withDuplicates.add("2");
    withDuplicates.add("1");
    withDuplicates.add("3");
    HashSet<String> set = new HashSet<>(withDuplicates);
    ArrayList<String> withoutDupicates = new ArrayList<>(set);

    ArrayList<String> duplicates = new ArrayList<String>();

    Iterator<String> 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);

Essa resposta foi escrita em Kotlin, mas pode ser facilmente traduzida para Java.

Se o tamanho do seu arraylist estiver dentro de uma pequena faixa fixa, esta é uma ótima solução.

var duplicateDetected = false
    if(arrList.size > 1){
        for(i in 0 until arrList.size){
            for(j in 0 until arrList.size){
                if(i != j && arrList.get(i) == arrList.get(j)){
                    duplicateDetected = true
                }
            }
        }
    }

private boolean isDuplicate() {
    for (int i = 0; i < arrayList.size(); i++) {
        for (int j = i + 1; j < arrayList.size(); j++) {
            if (arrayList.get(i).getName().trim().equalsIgnoreCase(arrayList.get(j).getName().trim())) {
                return true;
            }
        }
    }

    return false;
}