Java : Détecter les doublons dans ArrayList ?

Question

Comment pourrais-je détecter (en retournant vrai/faux) si une ArrayList contient plus d'un élément identique en Java ?

Merci beaucoup, Terry

Modifier J'ai oublié de préciser 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() ;

Answer 1

J'avais besoin de faire une opération similaire pour un Stream mais je n'ai pas trouvé de 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 des doublons sont trouvés dès le début plutôt que de devoir traiter tout le flux et ce n'est pas beaucoup plus compliqué que de tout mettre dans un fichier de type Set et en vérifiant la taille. Donc ce cas serait en gros :

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

Answer 2

Si vos éléments sont d'une manière ou d'une autre comparables (le fait que l'ordre ait une signification réelle est indifférent -- il faut juste qu'il soit cohérent avec votre définition de l'égalité), la solution la plus rapide pour supprimer les doublons est de trier la liste ( 0(n log(n))) puis de faire un seul passage et de rechercher répétées éléments (c'est-à-dire des éléments égaux qui se suivent) (c'est O(n)).

La complexité globale sera O(n log(n)), ce qui est à peu près la même que ce que vous obtiendriez avec un ensemble (n fois long(n)), mais avec une constante beaucoup plus petite. Ceci est dû au fait que la constante de sort/dedup résulte du coût de la comparaison des éléments, alors que le coût de l'ensemble résulte très probablement 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, car une implémentation basée sur l'arbre vous donnera un coût de O( n log²(n) ), ce qui est encore pire.

Cependant, d'après ce que j'ai compris, vous n'avez pas besoin de supprimer duplicata, mais se contentent de tester leur existence. Vous devriez donc coder manuellement un algorithme de tri par fusion ou par tas sur votre tableau, qui sortirait simplement en retournant true (i.e. "there is a dup") si votre comparateur retourne 0, et sinon terminerait le tri, et traverserait le tableau trié en 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 de doublons, à moins que les deux éléments ne soient déjà à leur position finale (ce qui est peu probable). Ainsi, un algorithme de tri modifié devrait permettre une amélioration considérable des performances (il faudrait que je le prouve, mais je suppose que l'algorithme modifié devrait être dans la gamme O(log(n)) sur des données uniformément aléatoires).

Answer 3

Si vous voulez l'ensemble des valeurs dupliquées :

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 aussi probablement à rogner les valeurs ou à utiliser des minuscules ... selon votre cas.

Answer 4

En termes simples : 1) s'assurer que tous les éléments sont comparables 2) trier le tableau 2) itérer sur le tableau et trouver les doublons

Answer 5

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