Identifizieren Sie Duplikate in einer Liste

Ich habe eine Liste vom Typ Integer, zB:

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

Ich möchte eine Methode, um alle Duplikate zurückzugeben, z.

[1, 3]

Was ist der beste Weg, dies zu tun?

Das Verfahren addvon Setliefert einen boolean , ob ein Wert bereits vorhanden ist (true , wenn es nicht vorhanden ist , falsch , wenn es bereits vorhanden ist , siehe Set - Dokumentation ).

Durchlaufen Sie einfach alle Werte:

public Set<Integer> findDuplicates(List<Integer> listContainingDuplicates)
{ 
  final Set<Integer> setToReturn = new HashSet<>(); 
  final Set<Integer> set1 = new HashSet<>();

  for (Integer yourInt : listContainingDuplicates)
  {
   if (!set1.add(yourInt))
   {
    setToReturn.add(yourInt);
   }
  }
  return setToReturn;
}

Ich brauchte auch dafür eine Lösung. Ich habe die Lösung von Leifg verwendet und sie generisch gemacht.

private <T> Set<T> findDuplicates(Collection<T> collection) {

    Set<T> duplicates = new LinkedHashSet<>();
    Set<T> uniques = new HashSet<>();

    for(T t : collection) {
        if(!uniques.add(t)) {
            duplicates.add(t);
        }
    }

    return duplicates;
}

Ich nahm John Stricklers Lösung und machte sie neu, um die in JDK8 eingeführte Streams-API zu verwenden:

private <T> Set<T> findDuplicates(Collection<T> collection) {
    Set<T> uniques = new HashSet<>();
    return collection.stream()
        .filter(e -> !uniques.add(e))
        .collect(Collectors.toSet());
}

Hier ist eine Lösung mit Streams mit Java 8

// lets assume the original list is filled with {1,1,2,3,6,3,8,7}
List<String> original = new ArrayList<>();
List<String> result = new ArrayList<>();

Sie sehen nur, ob die Häufigkeit dieses Objekts mehr als einmal in Ihrer Liste enthalten ist. Rufen Sie dann .distinct () auf, um nur eindeutige Elemente in Ihrem Ergebnis zu haben

result = original.stream()
    .filter(e -> Collections.frequency(original, e) > 1)
    .distinct()
    .collect(Collectors.toList());
// returns {1,3}
// returns only numbers which occur more than once

result = original.stream()
    .filter(e -> Collections.frequency(original, e) == 1)
    .collect(Collectors.toList());
// returns {2,6,8,7}
// returns numbers which occur only once

result = original.stream()
    .distinct()
    .collect(Collectors.toList());
// returns {1,2,3,6,8,7}
// returns the list without duplicates

Java 8 Basislösung:

List duplicates =    
list.stream().collect(Collectors.groupingBy(Function.identity()))
    .entrySet()
    .stream()
    .filter(e -> e.getValue().size() > 1)
    .map(Map.Entry::getKey)
    .collect(Collectors.toList());

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

}

Natürlich können Sie mit ihnen machen, was Sie wollen (dh in ein Set einfügen, um eine eindeutige Liste doppelter Werte zu erhalten), anstatt zu drucken ... Dies hat auch den Vorteil, dass auch die Position doppelter Elemente aufgezeichnet wird.

Verwenden von Guava unter Java 8

private Set<Integer> findDuplicates(List<Integer> input) {
    // Linked* preserves insertion order so the returned Sets iteration order is somewhat like the original list
    LinkedHashMultiset<Integer> duplicates = LinkedHashMultiset.create(input);

    // Remove all entries with a count of 1
    duplicates.entrySet().removeIf(entry -> entry.getCount() == 1);

    return duplicates.elementSet();
}

Das funktioniert auch:

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

Sie können so etwas verwenden:

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

Lambas könnte eine Lösung sein

Integer[] nums =  new Integer[] {1, 1, 2, 3, 3, 3};
List<Integer> list = Arrays.asList(nums);

List<Integer> dps = list.stream().distinct().filter(entry -> Collections.frequency(list, entry) > 1).collect(Collectors.toList());

Verwenden Sie eine MultiMap, um jeden Wert als Schlüssel / Wertesatz zu speichern. Durchlaufen Sie dann die Schlüssel und suchen Sie diejenigen mit mehreren Werten.

Wenn Sie Eclipse-Sammlungen verwenden , funktioniert dies:

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

Update: Ab Eclipse Collections 9.2 können Sie jetzt verwendenselectDuplicates

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

Sie können auch primitive Sammlungen verwenden, um dies zu erreichen:

IntList list = IntLists.mutable.with(1, 1, 2, 3, 3, 3);
IntSet dupes = list.toBag().selectDuplicates().toSet();
Assert.assertEquals(IntSets.mutable.with(1, 3), dupes);

Hinweis: Ich bin ein Committer für Eclipse-Sammlungen.

public class practicese {
       public static void main(String[] args) {   

           List<Integer> listOf = new ArrayList<Integer>();
           listOf.add(3);
           listOf.add(1);
           listOf.add(2);
           listOf.add(3);
           listOf.add(3);
           listOf.add(2);
           listOf.add(1);

           List<Integer> tempList = new ArrayList<Integer>();
           for(Integer obj:listOf){
                if(!tempList.contains(obj)){
                    tempList.add(obj);

                }
            }
            System.out.println(tempList);

    }

}

Ähnlich wie bei einigen Antworten hier, aber wenn Sie Duplikate basierend auf einer Eigenschaft suchen möchten:

  public static <T, R> Set<R> findDuplicates(Collection<? extends T> collection, Function<? super T, ? extends R> mapper) {
    Set<R> uniques = new HashSet<>();
    return collection.stream()
        .map(mapper)
        .filter(e -> !uniques.add(e))
        .collect(toSet());
  }

Erstellen Sie eine Map<Integer,Integer>, iterieren Sie die Liste. Wenn sich ein Element in der Karte befindet, erhöhen Sie seinen Wert. Fügen Sie es andernfalls mit Schlüssel = 1
zur Karte hinzu. Iterieren Sie die Karte und fügen Sie alle Elemente mit Schlüssel> = 2 zu den Listen hinzu

public static void main(String[] args) {
        List<Integer> list = new LinkedList<Integer>();
        list.add(1);
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(3);
        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        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<Integer> result = new LinkedList<Integer>();
        for (Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 1) {
                result.add(entry.getKey());
            }
        }
        for (Integer x : result) { 
            System.out.println(x);
        }

    }

Kompakte generierte Version der Top-Antwort, außerdem leerer Scheck hinzugefügt und vorbelegt Set-Größe:

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

Ich nahm Sebastians Antwort und fügte einen keyExtractor hinzu -

    private <U, T> Set<T> findDuplicates(Collection<T> collection, Function<? super T,? extends U> keyExtractor) {
        Map<U, T> uniques = new HashMap<>(); // maps unique keys to corresponding values
        return collection.stream()
            .filter(e -> uniques.put(keyExtractor.apply(e), e) != null)
            .collect(Collectors.toSet());
    }

Eine thread-sichere Alternative ist folgende:

/**
 * Returns all duplicates that are in the list as a new {@link Set} thread-safe.
 * <p>
 * Usually the Set will contain only the last duplicate, however the decision
 * what elements are equal depends on the implementation of the {@link List}. An
 * exotic implementation of {@link List} might decide two elements are "equal",
 * in this case multiple duplicates might be returned.
 * 
 * @param <X>  The type of element to compare.
 * @param list The list that contains the elements, never <code>null</code>.
 * @return A set of all duplicates in the list. Returns only the last duplicate.
 */
public <X extends Object> Set<X> findDuplicates(List<X> list) {
    Set<X> dups = new LinkedHashSet<>(list.size());
    synchronized (list) {
        for (X x : list) {
            if (list.indexOf(x) != list.lastIndexOf(x)) {
                dups.add(x);
            }
        }
    }
    return dups;
}

Versuchen Sie dies, um doppelte Elemente in der Liste zu finden:

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

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

Dies sollte für sortiert und unsortiert funktionieren.

public void testFindDuplicates() {

    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(3);
    list.add(3);

    Set<Integer> result = new HashSet<Integer>();
    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));
}

Dies ist ein Problem, bei dem funktionale Techniken glänzen. Zum Beispiel ist die folgende F # -Lösung sowohl klarer als auch weniger fehleranfällig als die beste zwingende Java-Lösung (und ich arbeite täglich sowohl mit Java als auch mit F #).

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

Natürlich geht es bei dieser Frage um Java. Mein Vorschlag ist daher, eine Bibliothek zu verwenden, die Java Funktionsfunktionen bietet. Zum Beispiel könnte es mit meiner eigenen Bibliothek wie folgt gelöst werden (und es gibt auch einige andere, die einen Blick wert sind):

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

public class DuplicatesWithOutCollection {

    public static void main(String[] 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(String[] 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;
    }
}

Dies wäre eine gute Methode, um doppelte Werte zu finden, ohne Set zu verwenden.

public static <T> List<T> findDuplicates(List<T> list){

List<T> nonDistinctElements = new ArrayList<>();

  for(T s : list)
    if(list.indexOf(s) != list.lastIndexOf(s))
      if(!nonDistinctElements.contains(s))
        nonDistinctElements.add(s);

  return nonDistinctElements;
}

Angenommen, Sie möchten eine Methode, die Ihnen eine eindeutige Liste zurückgibt. Wenn Sie also eine Liste übergeben, in der Elemente mehr als einmal vorkommen, erhalten Sie eine Liste mit unterschiedlichen Elementen.

public static <T> void distinctList(List<T> list){

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

Und Version, die commons-collections CollectionUtils.getCardinalityMapMethode verwendet:

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

`` `

Wie wäre es mit diesem Code -

public static void main(String[] args) {

    //Lets say we have a elements in array
    int[] a = {13,65,13,67,88,65,88,23,65,88,92};

    List<Integer> ls1 = new ArrayList<>();
    List<Integer> ls2 = new ArrayList<>();
    Set<Integer> ls3 = new TreeSet<>();

    //Adding each element of the array in the list      
    for(int i=0;i<a.length;i++) {
     {
    ls1.add(a[i]);
    }
    }

    //Iterating each element in the arrary
    for (Integer eachInt : ls1) {

    //If the list2 contains the iterating element, then add that into set<> (as this would be a duplicate element)
        if(ls2.contains(eachInt)) {
            ls3.add(eachInt);
        }
        else {ls2.add(eachInt);}

    }

    System.out.println("Elements in array or ls1"+ls1); 
    System.out.println("Duplicate Elements in Set ls3"+ls3);


}

Nur für den Fall, dass Sie sowohl das Duplikat als auch das Nicht-Duplikat einschließen möchten. Grundsätzlich ist die Antwort der richtigen Antwort ähnlich, aber anstatt von einem Teil zurückzukehren, wenn nicht Teil, geben Sie den anderen Teil zurück

Verwenden Sie diesen Code (ändern Sie den gewünschten Typ)

public Set<String> findDup(List<String> Duplicates){
    Set<String> returning = new HashSet<>();
    Set<String> nonreturning = new HashSet<>();
    Set<String> setup = new HashSet<>();
    for(String i:Duplicates){
        if(!setup.add( i )){
            returning.add( i );
        }else{
            nonreturning.add( i );
        }
    }
    Toast.makeText( context,"hello set"+returning+nonreturning+" size"+nonreturning.size(),Toast.LENGTH_SHORT ).show();
    return nonreturning;
}

Allgemeinere Methode als Variante von https://stackoverflow.com/a/52296246

    /**
     * Returns a duplicated values found in given collection based on fieldClassifier
     *
     * @param collection given collection of elements
     * @param fieldClassifier field classifier which specifies element to check for duplicates(useful in complex objects).
     * @param <T> Type of element in collection
     * @param <K> Element which will be returned from method in fieldClassifier.
     * @return returns list of values that are duplocated.
     */
    public static <T, K> List<K> lookForDuplicates(List<T> collection, Function<? super T, ? extends K> fieldClassifier) {

        return collection.stream().collect(Collectors.groupingBy(fieldClassifier))
                         .entrySet()
                         .stream()
                         .filter(e -> e.getValue().size() > 1)
                         .map(Map.Entry::getKey)
                         .collect(Collectors.toList());
    }

Wenn Sie den Maximalwert kennen (zum Beispiel <10000), können Sie Platz für Geschwindigkeit opfern. Ich kann mich nicht an den genauen Namen dieser Technik erinnern.

Pseudocode:

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

Versuchen Sie einfach Folgendes:

Beispiel, wenn Listenwerte sind: [1, 2, 3, 4, 5, 6, 4, 3, 7, 8] doppeltes Element [3, 4].

Collections.sort(list);
        List<Integer> 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);