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

Question

Ich habe ein Array von Objekten, die die Duplikate entfernt / gefiltert müssen. Ich wollte gerade equals & hachCode Elemente auf das Objekt zu überschreiben, und kleben Sie sie dann in einem Set ... aber ich dachte, ich sollte mindestens Umfrage Stackoverflow zu sehen, ob es eine andere Möglichkeit war, vielleicht einige clevere Methode einer anderen API?

Answer 1

Ich würde mit Ihrem Ansatz zustimmen hashCode() und equals() außer Kraft zu setzen und verwenden Sie etwas, das Set implementiert.

Dadurch wird auch völlig klar, zu anderen Entwicklern macht, dass die Nicht-Duplikat-Charakteristik erforderlich ist.

Ein weiterer Grund - Sie erhalten eine Implementierung zu wählen, die am besten Ihre Bedürfnisse erfüllt jetzt:

• HashSet
• TreeSet
• LinkedHashSet

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

Answer 2

Ich fand diese im Web

Hier sind zwei Methoden, mit denen Sie Duplikate in einer Arraylist zu entfernen. removeDuplicate nicht die Reihenfolge halten, wo als removeDuplicateWithOrder den Auftrag mit einem gewissen Leistungsaufwand unterhä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 3

Aufschalten equals und hashCode und die Schaffung eines Satzes war mein erster Gedanke auch. Es ist gut, Praxis einige überschriebene Version dieser Methoden hat sowieso in Ihrer Vererbungshierarchie.

I denken , wenn Sie einen LinkedHashSet verwenden werden Sie sogar um einzigartige Elemente bewahren ...

Answer 4

Im Grunde wollen Sie eine LinkedHashSet<T>-Implementierung, die die List<T> Schnittstelle für den Direktzugriff unterstützt. Daher ist dies, 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ürden die zugrunde liegende LinkedHashSet<T> zugreifen und diese manipulieren. Der Trick ist, diese Klasse zu haben, korrekt verhalten, wenn man versucht, Duplikate über die List<T> hinzufügen Methoden hinzuzufügen (eine Ausnahme oder Wieder Sie das Objekt zu einem anderen Index zu werfen Optionen wären: die Sie entweder eine oder konfigurierbar machen können wählen, wird von den Benutzern der Klasse).

Answer 5

eine Liste distinctList Verwenden Element beim ersten Mal aufzeichnen iterator hinein stolpern, kehrt der distinctList als Liste alle Duplikate entfernt

 private List removeDups(List list) {
        Set tempSet = new HashSet();
        List distinctList = new ArrayList();
        for(Iterator  it = list.iterator(); it.hasNext();) {
            Object next = it.next();
            if(tempSet.add(next)) {
                distinctList.add(next);
            } 
        }
        return distinctList;
   } 

Answer 6

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

Warum setzen sich an diesem Punkt überhaupt?

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

Verwenden Sie ein Set oder eine SortedSet zu allen Zeiten (wenn die Elemente eine natürliche Ordnung als auch haben), um die Elemente zu halten. Wenn Sie den Anzeigenauftrag zu halten brauchen, dann können Sie die LinkedHashSet verwenden, da es wurde darauf hingewiesen.

Mit auf Post-Prozess einige Datenstruktur ist oft ein Hinweis, dass Sie eine andere zu beginnen haben gewählt sollte.

Answer 7

Natürlich ist die Original-Beitrag stellt sich die Frage: „Wie Sie das Array erhalten haben (das könnte Einträge enthalten dupliziert) in erster Linie?“

Haben Sie das Array benötigen (mit Dubletten) für andere Zwecke, oder können Sie einfach einen Satz von Anfang an verwenden?

Alternativ, wenn Sie die Anzahl der Vorkommen von jedem Wert wissen müssen, könnten Sie eine Map<CustomObject, Integer> verwenden zählt zu verfolgen. Auch die Google Kollektionen Definition der Multimap Klassen können von Nutzen sein.

Answer 8

Ein Set ist definitiv die beste Wahl. Der einzige Weg, die Dinge aus einem Array entfernen (ohne einen neuen erstellen) ist sie auf Null, und dann am Ende mit vielen null-Kontrollen bis später.

Answer 9

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

Und wenn Sie 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 könnten wohl eine Pause hinzuzufügen; Anweisung nach der Zerstörung, aber dann entdecken Sie nur das erste Duplikat, aber wenn das alles ist, Sie jemals haben werden, dann wäre es eine nette kleine Optimierung sein.