Java: détecter les doublons dans ArrayList?

Comment pourrais-je détecter (renvoyer vrai / faux) si une ArrayList contient plusieurs éléments du même élément en Java?

Merci beaucoup, Terry

Edit Oublié de mentionner que je ne cherche pas à comparer les "blocs" entre eux mais leurs valeurs entières. Chaque "bloc" a un int et c'est ce qui les rend différents. Je trouve l'int d'un bloc particulier en appelant une méthode nommée "getNum" (par exemple table1 [0] [2] .getNum ();

Le plus simple: vider toute la collection dans un Set (en utilisant le constructeur Set (Collection) ou Set.addAll), puis voir si le Set a la même taille que ArrayList.

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

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

Mise à jour: si je comprends bien votre question, vous avez un tableau 2D de Block, comme dans

Table de bloc [] [];

et vous voulez détecter si une ligne d'entre eux a des doublons?

Dans ce cas, je pourrais faire ce qui suit, en supposant que Block implémente correctement "equals" et "hashCode":

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

Je ne suis pas sûr à 100% de cela pour la syntaxe, il serait donc plus sûr de l'écrire sous la forme

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.addrenvoie un booléen false si l'élément en cours d'ajout est déjà dans l'ensemble, vous pouvez donc même court-circuiter et expulser tout ajout qui retourne falsesi tout ce que vous voulez savoir est s'il y a des doublons.

Code amélioré, utilisant la valeur de retour de Set#addau lieu de comparer la taille de la liste et de l'ensemble.

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 du tout les doublons, vous devez simplement couper le processus intermédiaire de détection des doublons et utiliser un ensemble .

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

• Peut trouver des doublons dans une collection
• renvoyer 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 en quelque sorte 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 des doublons la plus rapide va trier la liste (0 (n log ( n))) puis pour faire une seule passe et chercher des éléments répétés (c'est-à-dire des éléments égaux qui se succèdent) (c'est O (n)).

La complexité globale va être O (n log (n)), ce qui est à peu près la même chose 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 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 de Set basée sur le hachage, c'est parce qu'une arborescence va vous donner un O (n log² (n)), ce qui est encore pire.

Si je comprends bien, cependant, vous n'avez pas besoin de supprimer les doublons, mais simplement de tester leur existence. Vous devez donc coder à la main un algorithme de fusion ou de tri de tas sur votre tableau, qui sort simplement en retournant true (c'est-à-dire "il y a un dup") si votre comparateur renvoie 0, et sinon termine le tri, et traverse le tableau trié testant les répétitions . Dans un tri par fusion ou par tas, en effet, lorsque le tri est terminé, vous aurez comparé chaque paire en double à moins que les deux éléments ne soient déjà dans leur position finale (ce qui est peu probable). Ainsi, un algorithme de tri modifié devrait apporter 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 pu trouver 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 de devoir traiter l'ensemble du flux et n'est pas beaucoup plus compliqué que de simplement tout mettre dans un Setet de vérifier la taille. Donc, ce cas serait à peu près:

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

Avec Java 8+, vous pouvez utiliser l'API Stream:

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

En termes simples: 1) assurez-vous que tous les éléments sont comparables 2) triez le tableau 2) parcourez le tableau et trouvez les doublons

Pour connaître les doublons dans une liste, utilisez le code suivant: Il vous donnera l'ensemble qui contient les 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;
  }

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

Imprimez simplement la liste des résultats et voyez le résultat sans doublons :)

Si vous voulez le jeu de valeurs en double:

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

Et pensez probablement aussi à rogner les valeurs ou à utiliser des minuscules ... selon votre cas.

    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 un impact majeur sur les performances 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 des questions biaisées posées lors des entretiens pour supprimer les doublons de la liste sans utiliser aucune autre collection, l'exemple ci-dessus est la réponse. Dans le monde réel cependant, si je dois y parvenir, je mettrai des éléments de liste à ensemble, 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 été substituée 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);

Cette réponse est écrite en Kotlin, mais peut facilement être traduite en Java.

Si la taille de votre arraylist est dans une petite plage fixe, alors c'est une excellente solution.

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