Java: Duplikate in ArrayList erkennen?

104

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


quelle
Wenn "Block" von einem int verglichen wird, sollte hashCode wahrscheinlich dasselbe int zurückgeben und diese Ints gleich vergleichen lassen.
Paul Tomblin
benutze Set anstelle von List
dmarquina

Antworten:

192

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.

Paul Tomblin
quelle
13
Stellen Sie sicher, dass Sie auch hashCode / equals implementieren.
jon077
1
Oder noch ein bisschen einfacher: Wickeln Sie es beim Erstellen des Sets ein, z. B. neues HashSet (Liste), anstatt addAll zu verwenden.
Fabian Steeg
2
@ jon077: Das hängt von deiner Definition von "Duplikat" ab.
Michael Myers
Wäre der Prozess der Erkennung der Elemente in einem 2D-Array der gleiche? Zum Beispiel von Array [0] [0] zu Array [0] [6] (eine 'Zeile') prüfen ..? Vielen Dank, Terry
Jedes Objekt im Array enthält einen ganzzahligen Wert. Bei "Duplizieren" hätte das Objekt den gleichen ganzzahligen Wert.
60

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;
}
akuhn
quelle
7
Wäre es effizienter, dem HashSet mitzuteilen, wie viel Speicherplatz zugewiesen werden soll : Set<T> set = new HashSet<T>(list.size());? Angesichts eines Listenparameters halte ich es für effizienter, wenn die Liste häufig keine Duplikate enthält.
Paul Jackson
1
@PaulJackson Die Größe basierend auf der vollständigen Liste wird wahrscheinlich von Vorteil sein. Wenn es jedoch häufig vorkommt, dass ein Duplikat frühzeitig gefunden wird, wurde der Speicherplatz verschwendet. Auch HashSetdie Größenanpassung auf die Größe der Liste führt aufgrund des zugrunde liegenden Ladefaktors der Hash-Struktur zu einer Größenänderung beim Durchlaufen der gesamten Liste.
Jay Anderson
Wenn Sie keine tatsächlichen Probleme mit der Laufzeit oder dem Speicherplatz haben, würde ich Ihren Code nicht so optimieren. Eine vorzeitige Optimierung wird am besten vermieden.
Akuhn
15

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

matt b
quelle
1
Stellen
@ jon077: Nicht unbedingt, wie ich gerade sagte.
Michael Myers
1
Allerdings mit einem Set nicht erkennen Duplikate. Es verhindert sie nur. Es sei denn, Sie überprüfen natürlich das Ergebnis der Add-Methode, wie oben von @akuhn angegeben.
Mcallahan
13

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;
}
user60062
quelle
Das ist ziemlich großartig. Sie haben einen ungültigen Code und vielleicht ist dies nicht der optimalste Weg, aber Ihr Ansatz rockt total! (und es funktioniert großartig)
Jules Colle
9

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

Varkhan
quelle
In diesem Fall ist n 6, sodass ich nicht viel Zeit mit Implementierungsdetails verschwenden würde, aber ich werde Ihre Vorstellung von der speziellen Heap-Sortierung behalten, wenn ich jemals so etwas tun muss.
Paul Tomblin
Ich verstehe den dritten Absatz nicht. Mergesort und Heapsort sind beim Schreiben beide O (nlog (n)) und nicht O (log (n)). Selbst wenn Sie beenden, sobald Sie ein Duplikat identifiziert haben, ändert dies nichts an Ihrer Zeitkomplexität ...
ChaimKut
8

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());
Jay Anderson
quelle
7

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();
}
Sergiy Dakhniy
quelle
2

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

Antonio
quelle
1

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;
  }
Rakesh Sabbani
quelle
1

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

Ashana.Jackol
quelle
1

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.

Saurabh
quelle
Einfachste und beste Antwort, wenn Sie die Duplikate möchten. Für die Leistung können Sie einen uniqueSet-Hinweis mit der Größe der Argumente einleiten.
Christophe Roussy
0
    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!

Amitesh Jha
quelle
0
/**
     * 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;
    }
}
faizal
quelle
0
    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);
Venkata
quelle
Fügen Sie eine Erklärung mit Antwort hinzu, wie diese Antwort OP bei der Behebung des aktuellen Problems
hilft
0

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
                }
            }
        }
    }
Grantespo
quelle
0
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;
}
Ketan Ramani
quelle