Каков наилучший способ удаления дубликатов в массиве в Java? - PullRequest
Новая
       60

Каков наилучший способ удаления дубликатов в массиве в Java?

15 голосов
/ 10 декабря 2008

У меня есть массив объектов, которые нуждаются в удалении / фильтрации дубликатов. Я собирался просто переопределить equals & hachCode для элементов Object, а затем вставить их в Set ... но я решил, что мне следует хотя бы опросить stackoverflow, чтобы увидеть, есть ли другой способ, возможно, какой-нибудь умный метод какого-то другого API?

Ответы [ 9 ]

21 голосов
/ 10 декабря 2008

Я бы согласился с вашим подходом переопределить hashCode() и equals() и использовать что-то, что реализует Set.

Это также делает абсолютно понятным для всех других разработчиков, что обязательна неповторяющаяся характеристика.

Другая причина - вы можете выбрать реализацию, которая лучше всего соответствует вашим потребностям:

и вам не нужно менять код, чтобы изменить реализацию в будущем.

9 голосов
/ 10 декабря 2008

Я нашел это в сети

Вот два метода, которые позволяют вам удалять дубликаты в ArrayList. removeDuplicate не поддерживает порядок, тогда как removeDuplicateWithOrder поддерживает порядок с некоторыми накладными расходами.

  1. Метод удаления дубликатов: 

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

  2. Метод removeDuplicateWithOrder: 

    /** 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);
}
3 голосов
/ 10 декабря 2008

Переопределение equals и hashCode и создание набора было моей первой мыслью тоже. В любом случае, рекомендуется иметь некоторые переопределенные версии этих методов в иерархии наследования.

Я думаю , что если вы используете LinkedHashSet, вы даже сохраните порядок уникальных элементов ...

2 голосов
/ 19 июня 2012

Использовать список distinctList , чтобы записать элемент в первый раз 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; }

2 голосов
/ 11 декабря 2008

По сути, вам нужна реализация LinkedHashSet<T>, которая поддерживает интерфейс List<T> для произвольного доступа. Следовательно, это то, что вам нужно:

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

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

}

Реализация методов List<T> позволит получить доступ к базовому LinkedHashSet<T> и управлять им. Хитрость заключается в том, чтобы этот класс вел себя корректно, когда кто-то пытается добавить дубликаты с помощью методов List<T> add (варианты выбора: исключение или повторное добавление элемента с другим индексом: вы можете выбрать один из них или сделать настраиваемым). пользователями класса).

1 голос
/ 11 декабря 2008

Конечно, в оригинальном посте напрашивается вопрос: «Как вы взяли этот массив (который может содержать дублированные записи)?»

Вам нужен массив (с дубликатами) для других целей, или вы могли бы просто использовать Set с самого начала?

В качестве альтернативы, если вам нужно знать количество вхождений каждого значения, вы можете использовать Map<CustomObject, Integer> для отслеживания количества. Также может использоваться определение Google Collections классов Multimap.

1 голос
/ 11 декабря 2008

Я хотел бы повторить замечание, высказанное Джейсоном в комментариях:

Зачем вообще ставить себя в эту точку?

Зачем использовать массив для структуры данных, которая вообще не должна содержать дубликаты?

Используйте Set или SortedSet (когда элементы также имеют естественный порядок) для хранения элементов. Если вам нужно сохранить порядок вставки, вы можете использовать LinkedHashSet, как было указано.

Необходимость пост-обработки некоторой структуры данных часто является намеком на то, что вам следовало выбрать другую для начала.

0 голосов
/ 10 декабря 2008

Исходя из общего стандарта программирования, вы всегда можете дважды перечислить коллекции, а затем сравнить источник и цель.

И если ваше внутреннее перечисление всегда начинается с одной записи после источника, это довольно эффективно (псевдокод для последующего выполнения) 

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

Вы могли бы добавить разрыв; заявление после уничтожения, но тогда вы обнаружите только первый дубликат, но если это все, что у вас когда-либо будет, то это будет хорошая небольшая оптимизация.

0 голосов
/ 10 декабря 2008

A Set определенно ваш лучший выбор. Единственный способ удалить вещи из массива (без создания нового) - это обнулить их, а затем вы получите множество нулевых проверок.

...