Как найти дубликаты в массиве

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

Задача

Итак, у нас есть массив. Это может быть массив любых объектов или примитивов. Для примера возьмём массив строк:

String[] animals = {"cat", "dog", "cow", "sheep", "cat", "dog"};

Теперь попробуем найти дублирующиеся строки в этом массиве.

Поиск дубликатов перебором

Сначала объявим вспомогательную коллекцию для хранения дубликатов – HashSet:

Set<T> duplicates = new HashSet<>();

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

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

for (int i = 0; i < a.length; i++) {
    T e1 = a[i];
    if (e1 == null) continue; // игнорируем null

    // сравниваем каждый элемент со всеми остальными
    for (int j = 0; j < a.length; j++) {
        if (i == j) continue; // не проверяем элемент с собой же
        T e2 = a[j];
        if (e1.equals(e2)) {
            // дубликат найден, сохраним его
            duplicates.add(e2);
        }
    }
}

И в конце возвратим найденные дубликаты:

return new ArrayList<>(duplicates);

Проверка

Проверим нашу программу:

String[] animals = {"cat", "dog", "cow", "sheep", "cat", "dog"};

System.out.println("Входной массив: " + Arrays.toString(animals));
System.out.println("Дубликаты: " + getDuplicatesWithIteration(animals));

Исходный код

package ru.javalessons.arrays;

import java.util.*;

public class ArrayFindDuplicates {
    public static void main(String[] args) {
        String[] animals = {"cat", "dog", "cow", "sheep", "cat", "dog"};

        System.out.println("Входной массив: " + Arrays.toString(animals));
        System.out.println("Дубликаты: " + getDuplicatesWithIteration(animals));
    }

    public static <T> List<T> getDuplicatesWithIteration(T[] a) {
        Set<T> duplicates = new HashSet<>();
        for (int i = 0; i < a.length; i++) {
            T e1 = a[i];
            if (e1 == null) continue; // игнорируем null

            // сравниваем каждый элемент со всеми остальными
            for (int j = 0; j < a.length; j++) {
                if (i == j) continue; // не проверяем элемент с собой же
                T e2 = a[j];
                if (e1.equals(e2)) {
                    // дубликат найден, сохраним его
                    duplicates.add(e2);
                }
            }
        }
        return new ArrayList<>(duplicates);
    }
}

Заключение

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