Was ist der beste Weg, um Duplikate in einem Array in Java zu entfernen?

Question

Ich habe ein Array von Objekten, die die Duplikate entfernt/gefiltert benötigen. Ich würde gleich & hachCode auf die Objektelemente überschreiben und sie dann in ein Set stecken ... aber ich dachte, ich sollte Stackoverflow abfragen, um zu sehen, ob es einen anderen Weg gab, vielleicht eine clevere Methode einer anderen API ?

Answer 1

Ich würde mit Ihrem Ansatz zu übersteuern hashCode() und equals() und etwas verwenden, das Set implementiert.

Dies macht auch für alle anderen Entwickler absolut klar, dass das Nicht-Duplikat-Merkmal erforderlich ist.

Ein weiterer Grund - Sie erhalten eine Implementierung zu wählen, die Ihren Bedürfnissen am besten entspricht jetzt:

• HashSet
• TreeSet
• LinkedHashSet

und Sie müssen nicht Ihre ändern Code, um die Implementierung in der Zukunft zu ändern.

Answer 2

Ein Set ist definitiv Ihre beste Wette. Die einzige Möglichkeit, Dinge aus einem Array zu entfernen (ohne ein neues zu erstellen), besteht darin, sie aus dem Array zu entfernen. Am Ende gibt es dann eine Menge Null-Checks.

Answer 3

Overriding equals und hashCode und das Erstellen eines Sets war mein erster Gedanke auch. Es empfiehlt sich, eine überarbeitete Version dieser Methoden in Ihrer Vererbungshierarchie zu verwenden.

Ich denke , dass, wenn Sie einen LinkedHashSet verwenden erhalten Sie sogar um einzigartige Elemente ...

Answer 4

ich dies im Web gefunden

Hier sind zwei Methoden, die Ihnen erlauben, um Duplikate zu entfernen in einer ArrayList. removeDuplicate verwaltet nicht die Reihenfolge, in der removeDuplicateWithOrder die Reihenfolge mit einem gewissen Leistungsaufwand aufrechterhält.

1. Die removeDuplicate Methode:

   /** List order not maintained **/ 
   public static void removeDuplicate(ArrayList arlList) 
   { 
   HashSet h = new HashSet(arlList); 
   arlList.clear(); 
   arlList.addAll(h); 
   } 
   

2. Die removeDuplicateWithOrder Methode:

   /** List order maintained **/ 
   public static void removeDuplicateWithOrder(ArrayList arlList) 
   { 
       Set set = new HashSet(); 
       List newList = new ArrayList(); 
       for (Iterator iter = arlList.iterator(); iter.hasNext();) { 
        Object element = iter.next(); 
        if (set.add(element)) 
        newList.add(element); 
       } 
       arlList.clear(); 
       arlList.addAll(newList); 
   } 
   

Answer 5

von einer allgemeinen Programmierstandard Sprechen können Sie immer doppelt so viele Sammlungen aufzuzählen die dann vergleichen die Quelle und Ziel.

Und wenn Ihre innere Aufzählung immer einen Eintrag nach der Quelle beginnt, ist es ziemlich effizient (Pseudo-Code zu folgen)

foreach (array as source) 
{ 
    // keep track where we are in the array 
    place++; 
    // loop the array starting at the entry AFTER the current one we are comparing to 
    for (i=place+1; i < max(array); i++) 
    { 
     if (source === array[place]) 
     { 
      destroy(array[i]); 
     } 
    } 
} 

Sie wohl eine Pause hinzufügen könnte; Aussage nach dem zerstören, aber dann entdecken Sie nur das erste Duplikat, aber wenn das alles ist, was Sie jemals haben werden, dann wäre es eine nette kleine Optimierung.

Answer 6

Ich möchte den Punkt von Jason in den Kommentaren wiederholen:

Warum setzen Sie sich zu diesem Zeitpunkt überhaupt?

Warum ein Array für eine Datenstruktur verwenden, die überhaupt keine Duplikate enthalten sollte?

Verwenden Sie eine Set oder eine SortedSet (wenn die Elemente auch eine natürliche Reihenfolge haben), um die Elemente zu halten. Wenn Sie den Anzeigenauftrag beibehalten müssen, können Sie die LinkedHashSet wie angegeben verwenden.

Einige Datenstrukturen nachzubearbeiten ist oft ein Hinweis darauf, dass Sie zu Beginn eine andere gewählt haben sollten.

Answer 7

Natürlich wirft der ursprüngliche Post die Frage auf: "Wie haben Sie das Array (das könnte doppelte Einträge enthalten) an erster Stelle?"

Benötigen Sie das Array (mit Duplikaten) für andere Zwecke, oder könnten Sie einfach ein Set von Anfang an verwenden?

Wenn Sie die Anzahl der Vorkommen jedes Werts wissen müssen, können Sie alternativ auch Map<CustomObject, Integer> verwenden, um die Anzahl zu überwachen. Außerdem kann die Google Collections Definition der Multimap-Klassen von Nutzen sein.

Answer 8

Grundsätzlich möchten Sie eine LinkedHashSet<T> Implementierung, die die List<T> Schnittstelle für den wahlfreien Zugriff unterstützt. Daher ist es das, was Sie brauchen:

public class LinkedHashSetList<T> extends LinkedHashSet<T> implements List<T> {

// Implementations for List<T> methods here ...

}

Die Umsetzung der List<T> Methoden würde die zugrunde liegenden LinkedHashSet<T> Zugriff und Manipulation. Der Trick besteht darin, dass sich diese Klasse korrekt verhält, wenn man versucht, Duplikate über die List<T> add -Methoden hinzuzufügen (eine Exception auszulösen oder das Item bei einem anderen Index wieder hinzuzufügen) wären Optionen: Sie können diese auswählen oder konfigurierbar machen der Klasse).

Answer 9

eine Liste toRemove Verwenden Element beim ersten Mal iterator Stolpern hinein aufnehmen, danach, wenn Treffen wieder mit dem Element aufgezeichnet, entfernen Sie es iterator.remove()

 
private void removeDups(List list) { 
     List toRemove = new ArrayList(); 
     for(Iterator it = list.iterator(); it.hasNext();) { 
      Object next = it.next(); 
      if(!toRemove.contains(next)) { 
       toRemove.add(next); 
      } else { 
       it.remove(); 
      } 
     } 
     toremove.clear(); 
    }