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

Как я могу определить (вернуть истину / ложь), содержит ли ArrayList более одного и того же элемента в Java?

Большое спасибо, Терри

Изменить Забыл упомянуть, что я не хочу сравнивать «блоки» друг с другом, а сравнивать их целые числа. У каждого «блока» есть int, и это их отличает. Я нахожу int конкретного блока, вызывая метод с именем "getNum" (например, table1 [0] [2] .getNum ();

Самый простой: выгрузите всю коллекцию в Set (используя конструктор Set (Collection) или Set.addAll), затем посмотрите, имеет ли Set тот же размер, что и ArrayList.

List<Integer> list = ...;
Set<Integer> set = new HashSet<Integer>(list);

if(set.size() < list.size()){
    /* There are duplicates */
}

Обновление: если я правильно понимаю ваш вопрос, у вас есть 2-й массив блоков, как в

Таблица блоков [] [];

и вы хотите определить, есть ли дубликаты в какой-либо строке?

В этом случае я мог бы сделать следующее, предполагая, что Block правильно реализует «equals» и «hashCode»:

for (Block[] row : table) {
   Set set = new HashSet<Block>(); 
   for (Block cell : row) {
      set.add(cell);
   }
   if (set.size() < 6) { //has duplicate
   }
}

Я не уверен на 100% в этом синтаксисе, поэтому может быть безопаснее написать его как

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.addвозвращает логическое значение false, если добавляемый элемент уже находится в наборе, так что вы можете даже закоротить и выгрузить любое возвращаемое добавление, falseесли все, что вы хотите знать, - есть ли какие-либо дубликаты.

Улучшенный код, использующий возвращаемое значение 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)), что примерно такое же, как у Set (n times long (n)), но с гораздо меньшей константой. Это связано с тем, что константа в сортировке / дедупликации является результатом стоимости сравнения элементов, тогда как стоимость из набора, скорее всего, будет результатом вычисления хеша плюс одно (возможно, несколько) сравнений хешей. Если вы используете реализацию Set на основе хэшей, то есть потому, что Tree based даст вам O (n log² (n)), что еще хуже.

Однако, насколько я понимаю, вам не нужно удалять дубликаты, а просто проверять их наличие. Таким образом, вы должны вручную запрограммировать алгоритм сортировки слияния или кучи в своем массиве, который просто завершает работу с возвратом истины (т. Е. «Есть дублирование»), если ваш компаратор возвращает 0, и в противном случае завершает сортировку и проходит тестирование отсортированного массива на наличие повторов. . Действительно, при сортировке слиянием или кучей, когда сортировка завершена, вы будете сравнивать каждую повторяющуюся пару, если оба элемента уже не были в своих конечных положениях (что маловероятно). Таким образом, измененный алгоритм сортировки должен дать огромное улучшение производительности (мне нужно было бы это доказать, но я думаю, что измененный алгоритм должен быть в O (log (n)) для равномерно случайных данных)

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

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

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

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

С Java 8+ вы можете использовать Stream API:

boolean areAllDistinct(List<Block> blocksList) {
    return blocksList.stream().map(Block::getNum).distinct().count() == blockList.size();
}

Проще говоря: 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;
  }

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

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

Если вам нужен набор повторяющихся значений:

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

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

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

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

Этот ответ написан на Kotlin, но его легко перевести на Java.

Если размер вашего Arraylist находится в фиксированном небольшом диапазоне, это отличное решение.

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

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