Java: обнаружение дубликатов в ArrayList?

улучшенный код, используя возвращаемое значение Set#add вместо сравнения размера списка и набора.

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

Если вы хотите избежать дублирования вообще, то вы должны просто вырезать средний процесс обнаружения дубликатов и использовать 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;
}

Если ваши элементы каким-то образом сопоставимы (тот факт, что порядок имеет какое-либо реальное значение, безразличен-он просто должен соответствовать вашему определению равенства), самое быстрое решение для удаления дубликатов будет сортировать список ( 0(n log(n))), а затем сделать один проход и искать повторное элементы (то есть равные элементы, которые следуют друг за другом) (Это O (n)).

общая сложность будет O (N log(n)), что примерно равно что вы получите с набором (n раз длиной (n)), но с гораздо меньшей константой. Это связано с тем, что константа в сортировке/дедупликации является результатом стоимости сравнения элементов, тогда как стоимость из набора, скорее всего, будет результатом вычисления хэша плюс одно (возможно, несколько) хэш-сравнений. Если вы используете реализацию набора на основе хэша, то есть потому, что дерево на основе даст вам O( n log2(n)), что еще хуже.

Как я понимаю, однако, вам это не нужно к удалить дубликаты, а просто проверить их существование. Таким образом, вы должны вручную закодировать алгоритм сортировки слияния или кучи в своем массиве, который просто завершает возврат true (т. е. "есть dup"), если ваш компаратор возвращает 0, а в противном случае завершает сортировку и проходит проверку отсортированного массива на повторения. В слиянии или сортировке кучи, действительно, когда сортировка будет завершена, вы будете сравнивать каждую повторяющуюся пару, если оба элемента уже не были в своих конечных позициях (что является вряд ли.) Таким образом, измененный алгоритм сортировки должен дать огромное улучшение производительности (я должен был бы доказать это, но я думаю, что измененный алгоритм должен быть в O(log(n)) на равномерно случайных данных)

мне нужно было сделать аналогичную операцию для Stream, но не смог найти хороший пример. Вот что я придумал.

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

это имеет преимущество короткого замыкания, когда дубликаты найдены рано, а не для обработки всего потока и не намного сложнее, чем просто положить все в Set и проверяя размер. Так что этот случай будет примерно:

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

проще говоря: 1) Убедитесь, что все элементы сравнимы 2) сортировка массива 2) перебираем массив и находим дубликаты

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

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

    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
    }

Примечание: это будет иметь большой хит производительности, хотя как элементы удаляются из начала списка. Для решения этой проблемы у нас есть два варианта. 1) повторите в обратном порядке и удалите элементы. 2) Используйте LinkedList вместо ArrayList. Из-за предвзятых вопросов, задаваемых в интервью, чтобы удалить дубликаты из списка без использования какой-либо другой коллекции, приведенный выше пример является ответом. В реальном мире, хотя, если я должен достичь этого, я поставлю элементы из списка, чтобы установить, просто!

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

пример конкретного класса, который был переопределен 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;
    }
}

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

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

лучший способ решить эту проблему-использовать 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);

просто печати результат arraylist и посмотреть результат без дубликатов :)