Java: Duplikate in ArrayList erkennen?

Wie kann ich feststellen (true / false zurückgeben), ob eine ArrayList mehr als ein Element in Java enthält?

Vielen Dank, Terry

Bearbeiten Vergessen, um zu erwähnen, dass ich nicht "Blöcke" miteinander vergleichen möchte, sondern deren ganzzahlige Werte. Jeder "Block" hat ein int und das macht sie anders. Ich finde das int eines bestimmten Blocks, indem ich eine Methode namens "getNum" aufrufe (z. B. table1 [0] [2] .getNum ();

Am einfachsten: Speichern Sie die gesamte Sammlung in einem Set (mithilfe des Set-Konstruktors (Collection) oder von Set.addAll) und prüfen Sie, ob das Set dieselbe Größe wie die ArrayList hat.

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

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

Update: Wenn ich Ihre Frage richtig verstehe, haben Sie ein 2D-Array von Block, wie in

Blocktabelle [] [];

und Sie möchten feststellen, ob eine Reihe von ihnen Duplikate enthält?

In diesem Fall könnte ich Folgendes tun, vorausgesetzt, Block implementiert "equals" und "hashCode" korrekt:

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

Ich bin mir der Syntax nicht 100% sicher, daher ist es möglicherweise sicherer, sie als zu schreiben

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.addGibt einen booleschen Wert false zurück, wenn sich das hinzugefügte Element bereits im Satz befindet. Sie können also sogar einen Kurzschluss kurzschließen und einen Fehler beheben, der zurückgegeben wird, falsewenn Sie nur wissen möchten, ob Duplikate vorhanden sind.

Verbesserter Code, der den Rückgabewert von verwendet, Set#addanstatt die Größe der Liste und des Satzes zu vergleichen.

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

Wenn Sie Duplikate vermeiden möchten, sollten Sie nur den mittleren Prozess zum Erkennen von Duplikaten ausschließen und ein Set verwenden .

Verbesserter Code zur Rückgabe der doppelten Elemente

• Kann Duplikate in einer Sammlung finden
• Geben Sie den Satz von Duplikaten zurück
• Einzigartige Elemente erhalten Sie aus dem Set

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

Wenn Ihre Elemente irgendwie vergleichbar sind (die Tatsache, dass die Reihenfolge eine echte Bedeutung hat, ist gleichgültig - sie muss nur mit Ihrer Definition der Gleichheit übereinstimmen), sortiert die schnellste Lösung zum Entfernen von Duplikaten die Liste (0 (n log ()))))))) n))), um dann einen einzelnen Durchgang durchzuführen und nach wiederholten Elementen zu suchen (dh nach gleichen Elementen, die aufeinander folgen) (dies ist O (n)).

Die Gesamtkomplexität wird O (n log (n)) sein, was ungefähr dem entspricht, was Sie mit einem Set (n-mal lang (n)) erhalten würden, jedoch mit einer viel kleineren Konstante. Dies liegt daran, dass die Konstante in sort / dedup aus den Kosten für den Vergleich von Elementen resultiert, während die Kosten aus der Menge höchstwahrscheinlich aus einer Hash-Berechnung plus einem (möglicherweise mehreren) Hash-Vergleich resultieren. Wenn Sie eine Hash-basierte Set-Implementierung verwenden, bedeutet dies, dass eine Tree-basierte Implementierung ein O (n log² (n)) ergibt, was noch schlimmer ist.

Nach meinem Verständnis müssen Sie jedoch keine Duplikate entfernen , sondern lediglich ihre Existenz testen. Sie sollten also einen Zusammenführungs- oder Heap-Sortieralgorithmus in Ihrem Array von Hand codieren, der einfach die Rückgabe von true beendet (dh "es gibt ein Dup"), wenn Ihr Komparator 0 zurückgibt, andernfalls die Sortierung abschließt und den sortierten Array-Test auf Wiederholungen durchläuft . Bei einer Zusammenführungs- oder Heap-Sortierung haben Sie tatsächlich nach Abschluss der Sortierung jedes doppelte Paar verglichen, es sei denn, beide Elemente befanden sich bereits an ihrer endgültigen Position (was unwahrscheinlich ist). Daher sollte ein optimierter Sortieralgorithmus eine enorme Leistungsverbesserung bringen (das müsste ich beweisen, aber ich denke, der optimierte Algorithmus sollte bei einheitlich zufälligen Daten im O (log (n)) sein).

Ich musste eine ähnliche Operation für a durchführen Stream, konnte aber kein gutes Beispiel finden. Folgendes habe ich mir ausgedacht.

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

Dies hat den Vorteil eines Kurzschlusses, wenn Duplikate frühzeitig gefunden werden, anstatt den gesamten Stream verarbeiten zu müssen, und ist nicht viel komplizierter, als einfach alles in einen zu setzen Setund die Größe zu überprüfen. Dieser Fall wäre also ungefähr:

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

Mit Java 8+ können Sie die Stream-API verwenden:

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

Einfach ausgedrückt: 1) Stellen Sie sicher, dass alle Elemente vergleichbar sind. 2) Sortieren Sie das Array. 2) Durchlaufen Sie das Array und suchen Sie nach Duplikaten

Um die Duplikate in einer Liste zu kennen, verwenden Sie den folgenden Code: Sie erhalten den Satz, der Duplikate enthält.

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

Der beste Weg, um dieses Problem zu lösen, ist die Verwendung eines 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);

Drucken Sie einfach die Ergebnis- Arrayliste aus und sehen Sie das Ergebnis ohne Duplikate :)

Wenn Sie doppelte Werte wünschen:

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

Und denken Sie wahrscheinlich auch daran, Werte zu kürzen oder Kleinbuchstaben zu verwenden ... je nach Fall.

    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
    }

Hinweis: Dies hat jedoch erhebliche Leistungseinbußen zur Folge, da Elemente vom Anfang der Liste entfernt werden. Um dies zu beheben, haben wir zwei Möglichkeiten. 1) in umgekehrter Reihenfolge iterieren und Elemente entfernen. 2) Verwenden Sie LinkedList anstelle von ArrayList. Aufgrund voreingenommener Fragen, die in Interviews gestellt wurden, um Duplikate aus der Liste zu entfernen, ohne eine andere Sammlung zu verwenden, ist das obige Beispiel die Antwort. In der realen Welt werde ich, wenn ich dies erreichen muss, einfach Elemente von List zu Set setzen!

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

Ein Beispiel für eine konkrete Klasse, die überschrieben wurde 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);

Diese Antwort ist in Kotlin geschrieben, kann aber leicht nach Java übersetzt werden.

Wenn die Größe Ihrer Arrayliste in einem festgelegten kleinen Bereich liegt, ist dies eine großartige Lösung.

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