Identifier les doublons dans une liste

J’ai une liste de type entier par exemple:

[1, 1, 2, 3, 3, 3] 

Je voudrais une méthode pour retourner tous les doublons, par exemple:

 [1, 3] 

Quelle est la meilleure façon de procéder?

La méthode add de Set renvoie un booléen indiquant si une valeur existe déjà (true s’il n’existe pas, false s’il existe déjà, voir Définition de la documentation ).

Il suffit donc de parcourir toutes les valeurs:

 public Set findDuplicates(List listContainingDuplicates) { final Set setToReturn = new HashSet(); final Set set1 = new HashSet(); for (Integer yourInt : listContainingDuplicates) { if (!set1.add(yourInt)) { setToReturn.add(yourInt); } } return setToReturn; } 

J’avais aussi besoin d’une solution. J’ai utilisé la solution de leifg et l’ai rendue générique.

 private  Set findDuplicates(Collection list) { Set duplicates = new LinkedHashSet(); Set uniques = new HashSet(); for(T t : list) { if(!uniques.add(t)) { duplicates.add(t); } } return duplicates; } 

J’ai pris la solution de John Ssortingckler et l’ai refaite pour utiliser l’API de stream introduite dans JDK8:

 private  Set findDuplicates(Collection collection) { Set uniques = new HashSet<>(); return collection.stream() .filter(e -> !uniques.add(e)) .collect(Collectors.toSet()); } 
 int[] nums = new int[] {1, 1, 2, 3, 3, 3}; Arrays.sort(nums); for (int i = 0; i < nums.length-1; i++) { if (nums[i] == nums[i+1]) { System.out.println("duplicate item "+nums[i+1]+" at Location"+(i+1) ); } } 

Évidemment, vous pouvez faire ce que vous voulez avec (c.-à-d. Mettre un ensemble pour obtenir une liste unique de valeurs en double) au lieu d'imprimer ... Cela a également l'avantage d'enregistrer l'emplacement des éléments en double.

Utiliser Guava sur Java 8

 private Set findDuplicates(List input) { // Linked* preserves insertion order so the returned Sets iteration order is somewhat like the original list LinkedHashMultiset duplicates = LinkedHashMultiset.create(input); // Remove all ensortinges with a count of 1 duplicates.entrySet().removeIf(entry -> entry.getCount() == 1); return duplicates.elementSet(); } 

Cela fonctionne aussi:

 public static Set findDuplicates(List input) { List copy = new ArrayList(input); for (Integer value : new HashSet(input)) { copy.remove(value); } return new HashSet(copy); } 

Vous pouvez utiliser quelque chose comme ceci:

 List newList = new ArrayList(); for(int i : yourOldList) { yourOldList.remove(i); if(yourOldList.contains(i) && !newList.contains(i)) newList.add(i); } 

Utilisez un MultiMap pour stocker chaque valeur en tant que jeu de clés / valeur. Ensuite, parcourez les touches et trouvez celles qui ont plusieurs valeurs.

Lambas pourrait être une solution

 Integer[] nums = new Integer[] {1, 1, 2, 3, 3, 3}; List list = Arrays.asList(nums); List dps = list.stream().distinct().filter(entry -> Collections.frequency(list, entry) > 1).collect(Collectors.toList()); 

Si vous utilisez les collections Eclipse , cela fonctionnera:

 MutableList list = Lists.mutable.with(1, 1, 2, 3, 3, 3); Set dupes = list.toBag().selectByOccurrences(i -> i > 1).toSet(); Assert.assertEquals(Sets.mutable.with(1, 3), dupes); 

Mise à jour: à partir des collections Eclipse 9.2, vous pouvez maintenant utiliser selectDuplicates

 MutableList list = Lists.mutable.with(1, 1, 2, 3, 3, 3); Set dupes = list.toBag().selectDuplicates().toSet(); Assert.assertEquals(Sets.mutable.with(1, 3), dupes); 

Note: Je suis un committer pour les collections Eclipse.

C’est un problème où les techniques fonctionnelles brillent. Par exemple, la solution F # suivante est à la fois plus claire et moins sujette aux bogues que la meilleure solution Java impérative (et je travaille quotidiennement avec Java et F #).

 [1;1;2;3;3;3] |> Seq.countBy id |> Seq.choose (fun (key,count) -> if count > 1 then Some(key) else None) 

Bien sûr, cette question concerne Java. Donc, ma suggestion est d’adopter une bibliothèque qui apporte des fonctionnalités fonctionnelles à Java. Par exemple, il pourrait être résolu en utilisant ma propre bibliothèque comme suit (et il y en a plusieurs autres qui valent la peine d’être examinées):

 Seq.of(1,1,2,3,3,3) .groupBy(new Func1() { public Integer call(Integer key) { return key; } }).filter(new Predicate>() { public Boolean call(Grouping grouping) { return grouping.getGrouping().count() > 1; } }).map(new Func1,Integer>() { public Integer call(Grouping grouping) { return grouping.getKey(); } }); 

Version généralisée compacte de la réponse supérieure, a également ajouté un chèque vide et une taille pré-allouée:

 public static final  Set findDuplicates(final List listWhichMayHaveDuplicates) { final Set duplicates = new HashSet<>(); final int listSize = listWhichMayHaveDuplicates.size(); if (listSize > 0) { final Set tempSet = new HashSet<>(listSize); for (final T element : listWhichMayHaveDuplicates) { if (!tempSet.add(element)) { duplicates.add(element); } } } return duplicates; } 

Essayez ceci pour trouver des éléments en double dans la liste:

 ArrayList arrayList1 = new ArrayList(); arrayList1.add("A"); arrayList1.add("A"); arrayList1.add("B"); arrayList1.add("B"); arrayList1.add("B"); arrayList1.add("C"); for (int x=0; x< arrayList1.size(); x++) { System.out.println("arrayList1 :"+arrayList1.get(x)); } Set s=new TreeSet(); s.addAll(arrayList1); Iterator it=s.iterator(); while (it.hasNext()) { System.out.println("Set :"+(String)it.next()); } 

Mettez la liste dans la liste (cela filtre uniquement les éléments uniques), supprimez tous les éléments de la liste d’origine (elle ne contiendra donc que les éléments ayant plus d’une occurrence), et mettez la liste dans un nouvel ensemble articles):

 List list = ...; list.removeAll(new HashSet(list)); return new HashSet(list); 

créer une Map , itérer la liste, si un élément est dans la map, augmenter sa valeur, sinon l’append à la map avec la clé = 1
itérer la carte et append aux listes tous les éléments avec la clé> = 2

 public static void main(Ssortingng[] args) { List list = new LinkedList(); list.add(1); list.add(1); list.add(1); list.add(2); list.add(3); list.add(3); Map map = new HashMap(); for (Integer x : list) { Integer val = map.get(x); if (val == null) { map.put(x,1); } else { map.remove(x); map.put(x,val+1); } } List result = new LinkedList(); for (Entry entry : map.entrySet()) { if (entry.getValue() > 1) { result.add(entry.getKey()); } } for (Integer x : result) { System.out.println(x); } } 

Cela devrait fonctionner pour sortingé et non sortingé.

 public void testFindDuplicates() { List list = new ArrayList(); list.add(1); list.add(1); list.add(2); list.add(3); list.add(3); list.add(3); Set result = new HashSet(); int currentIndex = 0; for (Integer i : list) { if (!result.contains(i) && list.subList(currentIndex + 1, list.size()).contains(i)) { result.add(i); } currentIndex++; } assertEquals(2, result.size()); assertTrue(result.contains(1)); assertTrue(result.contains(3)); } 
 public class DuplicatesWithOutCollection { public static void main(Ssortingng[] args) { int[] arr = new int[] { 2, 3, 4, 6, 6, 8, 10, 10, 10, 11, 12, 12 }; boolean flag = false; int k = 1; while (k == 1) { arr = removeDuplicate(arr); flag = checkDuplicate(arr, flag); if (flag) { k = 1; } else { k = 0; } } } private static boolean checkDuplicate(int[] arr, boolean flag) { int i = 0; while (i < arr.length - 1) { if (arr[i] == arr[i + 1]) { flag = true; } else { flag = false; } i++; } return flag; } private static int[] removeDuplicate(int[] arr) { int i = 0, j = 0; int[] temp = new int[arr.length]; while (i < arr.length - 1) { if (arr[i] == arr[i + 1]) { temp[j] = arr[i + 1]; i = i + 2; } else { temp[j] = arr[i]; i = i + 1; if (i == arr.length - 1) { temp[j + 1] = arr[i + 1]; break; } } j++; } System.out.println(); return temp; } } 
 import java.util.Scanner; public class OnlyDuplicates { public static void main(Ssortingng[] args) { System.out.print(" Enter a set of 10 numbers: "); int[] numbers = new int[10]; Scanner input = new Scanner(System.in); for (int i = 0; i < numbers.length; i++) { numbers[i] = input.nextInt(); } numbers = onlyDuplicates(numbers); System.out.print(" The numbers are: "); for (int i = 0; i < numbers.length; i++) { System.out.print(numbers[i] + ""); } } public static int[] onlyDuplicates(int[] list) { boolean flag = true; int[] array = new int[0]; array = add2Array(array, list[0]); for (int i = 0; i < list.length; i++) { for (int j = 0; j < array.length; j++) { if (list[i] == array[j]) { flag = false; break; } } if (flag) { array = add2Array(array, list[i]); } flag = true; } return array; } // Copy numbers1 to numbers2 // If the length of numbers2 is less then numbers2, return false public static boolean copyArray(int[] source, int[] dest) { if (source.length > dest.length) { return false; } for (int i = 0; i < source.length; i++) { dest[i] = source[i]; } return true; } // Increase array size by one and add integer to the end of the array public static int[] add2Array(int[] source, int data) { int[] dest = new int[source.length + 1]; copyArray(source, dest); dest[source.length] = data; return dest; } } 
 public class practicese { public static void main(Ssortingng[] args) { List listOf = new ArrayList(); listOf.add(3); listOf.add(1); listOf.add(2); listOf.add(3); listOf.add(3); listOf.add(2); listOf.add(1); List tempList = new ArrayList(); for(Integer obj:listOf){ if(!tempList.contains(obj)){ tempList.add(obj); } } System.out.println(tempList); } } 

Ce serait une bonne méthode pour trouver des valeurs en double sans utiliser Set.

 public static  List findDuplicates(List list){ List nonDistinctElements = new ArrayList<>(); for(T s : list) if(list.indexOf(s) != list.lastIndexOf(s)) if(!nonDistinctElements.contains(s)) nonDistinctElements.add(s); return nonDistinctElements; } 

Et dites que vous voulez une méthode qui vous renvoie une liste distincte, c’est-à-dire que si vous passez une liste où des éléments se produisent plus d’une fois, vous obtenez une liste avec des éléments distincts.

 public static  void distinctList(List list){ List nonDistinctElements = new ArrayList<>(); for(T s : list) if(list.indexOf(s) != list.lastIndexOf(s)) nonDistinctElements.add(s); for(T nonDistinctElement : nonDistinctElements) if(list.indexOf(nonDistinctElement) != list.lastIndexOf(nonDistinctElement)) list.remove(nonDistinctElement); } 

Et la version qui utilise la méthode commons-collections CollectionUtils.getCardinalityMap :

 final List values = Arrays.asList(1, 1, 2, 3, 3, 3); final Map cardinalityMap = CollectionUtils.getCardinalityMap(values); System.out.println(cardinalityMap .entrySet() .stream().filter(e -> e.getValue() > 1) .map(e -> e.getKey()) .collect(Collectors.toList())); 

“ `

Si vous connaissez la valeur maximale (par exemple <10000), vous pouvez sacrifier de l'espace pour la vitesse. Je ne me souviens pas du nom exact de cette technique.

pseudo code:

 //does not handle case when mem allocation fails //probably can be extended to unknown values /larger values . maybe by sorting first public List GetDuplicates(int max) { //allocate and clear memory to 0/false bit[] buckets=new bit[max] memcpy(buckets,0,max); //find duplicates List result=new List(); foreach(int val in List) { if (buckets[val]) { result.add(value); } else { buckets[val]=1; } } return result } 

Essayez ceci:

Exemple si les valeurs de liste sont: [1, 2, 3, 4, 5, 6, 4, 3, 7, 8] élément dupliqué [3, 4].

 Collections.sort(list); List dup = new ArrayList<>(); for (int i = 0; i < list.size() - 1; i++) { if (list.get(i) == list.get(i + 1)) { if (!dup.contains(list.get(i + 1))) { dup.add(list.get(i + 1)); } } } System.out.println("duplicate item " + dup);