Java: détecter les doublons dans ArrayList?

Code amélioré, en utilisant la valeur de retour de Set#add au lieu de comparer la taille de list et set.

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

Si vous cherchez à éviter d'avoir des doublons, vous devriez simplement couper le processus intermédiaire de détection des doublons et utiliser un Set .

Code amélioré pour renvoyer les éléments en double

• peut trouver des doublons dans une Collection
• renvoie l'ensemble des doublons
• des éléments uniques peuvent être obtenus à partir de l'Ensemble

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

Si vos éléments sont comparables (le fait que l'ordre ait une signification réelle est indifférent - il doit juste être cohérent avec votre définition de l'égalité), la solution de suppression de doublons la plus rapide va trier la liste ( 0(n log(n)) ) Puis faire un seul passage et chercher répété éléments (c'est-à-dire, des éléments égaux qui se suivent) (c'est O(N))).

La complexité globale va être O(N log(n)), Ce Qui est à peu près le même que ce que vous obtiendriez avec un ensemble (n fois long(n)), mais avec une constante beaucoup plus petite. En effet, la constante de tri/dédup résulte du coût de la comparaison des éléments, alors que le coût de l'ensemble est le plus susceptible de résulter d'un calcul de hachage, plus une (éventuellement plusieurs) comparaisons de hachage. Si vous utilisez une implémentation D'ensemble basée sur le hachage, c'est-à-dire parce qu'une arborescence va vous donner un O( N log2(n)), ce qui est encore pire.

Si je comprends bien, cependant, vous n'avez pas besoin de Supprimer doublons, mais simplement tester leur existence. Donc, vous devriez coder à la main un algorithme de tri de fusion ou de tas sur votre tableau, qui quitte simplement le retour true (c'est-à-dire "il y a un dup") si votre comparateur renvoie 0, et sinon termine le tri, et traverse le tableau trié en testant les répétitions. Dans un tri de fusion ou de tas, en effet, lorsque le tri est terminé, vous aurez comparé chaque paire dupliquée sauf si les deux éléments étaient déjà dans leur position finale (ce qui est peu probable). Ainsi, une sorte peaufinée l'algorithme devrait donner une énorme amélioration des performances(je devrais le prouver, mais je suppose que l'algorithme modifié devrait être dans le o(log (n)) sur des données uniformément aléatoires)

J'avais besoin de faire une opération similaire pour un Stream, mais je n'ai pas trouvé un bon exemple. Voici ce que j'ai trouvé.

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

Cela a l'avantage de court-circuiter lorsque les doublons sont trouvés tôt plutôt que d'avoir à traiter tout le flux et n'est pas beaucoup plus compliqué que de simplement mettre tout dans un Set et vérifier la taille. Donc, ce cas serait à peu près:

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

Tout simplement: 1) Assurez-vous que tous les articles sont comparables 2) trier le tableau 2) itérer sur le tableau et trouver des doublons

Pour connaître les Doublons dans une Liste, utilisez le code suivant:Il vous donnera l'ensemble qui contient des doublons.

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

    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
    }

Remarque: cela aura des performances majeures, car les éléments sont supprimés du début de la liste. Pour résoudre ce problème, nous avons deux options. 1) itérer dans l'ordre inverse et supprimer des éléments. 2) Utilisez LinkedList au lieu de ArrayList. En raison de questions biaisées posées dans les entrevues pour supprimer les doublons de la liste sans utiliser d'autre collection, l'exemple ci-dessus est la réponse. Dans le monde réel cependant, si je dois y parvenir, je vais mettre des éléments de la liste à définir, simple!

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

Un exemple de classe concrète qui a remplacé 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<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);
    }
}

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

La meilleure façon de gérer ce problème est d'utiliser un 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);

, il suffit d'imprimer résultat liste de tableaux et de voir le résultat sans doublons :)