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

Question

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

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

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

Answer 1

Самый простой: выгрузить всю коллекцию в 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 */
}

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

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

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

В этом случае я мог бы сделать следующее, предполагая, что Блок правильно реализует "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]);

...

Answer 2

Усовершенствованный код, использующий возвращаемое значение 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;
}

Answer 3

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

Answer 4

Улучшен код для возврата дубликатов элементов

• Может найти дубликаты в коллекции
• вернуть набор дубликатов
• Уникальные элементы можно получить из набора

---

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

Answer 5

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

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

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

Answer 6

Мне нужно было сделать аналогичную операцию для 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());

Answer 7

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

Answer 8

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

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

Answer 9

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

Answer 10

Если вы хотите установить повторяющиеся значения:

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

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