Как проверить, содержит ли массив дубликаты в Java

Введение

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

Далее мы рассмотрим более эффективную технику, использующую структуру данных HashSet, и покажем, как использовать коллекции Java для более быстрого обнаружения дубликатов. Наконец, мы изучим, как сортировка массива может упростить процесс выявления дубликатов. К концу этого лабораторного занятия у вас будет несколько стратегий для обработки дубликатов элементов в массивах Java.

Skills Graph

Поиск дубликатов с использованием вложенных циклов

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

Сначала создадим новый Java-файл с именем FindDuplicatesNested.java в каталоге ~/project. Это можно сделать непосредственно в проводнике файлов WebIDE, щелкнув правой кнопкой мыши по папке project и выбрав "New File", а затем введя имя файла.

Теперь откройте файл FindDuplicatesNested.java в редакторе кода и добавьте следующий Java-код:

public class FindDuplicatesNested {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        System.out.println("Finding duplicate elements using nested loops:");

        // Use nested loops to compare each element with every other element
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                // If a duplicate is found (elements are equal and not the same element)
                if (numbers[i] == numbers[j]) {
                    System.out.println("Duplicate found: " + numbers[j]);
                }
            }
        }
    }
}

Разберем этот код:

• int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};: Эта строка объявляет целочисленный массив с именем numbers и инициализирует его некоторыми значениями, включая дубликаты.
• for (int i = 0; i < numbers.length; i++): Это внешний цикл. Он проходит по каждому элементу массива с использованием индекса i.
• for (int j = i + 1; j < numbers.length; j++): Это внутренний цикл. Для каждого элемента с индексом i он проходит по оставшимся элементам массива, начиная с элемента, следующего за индексом i. Это важно, чтобы избежать сравнения элемента с самим собой и повторного нахождения одной и той же пары дубликатов (например, сравнения индекса 1 с индексом 4 и затем индекса 4 с индексом 1).
• if (numbers[i] == numbers[j]): Это условие проверяет, равен ли элемент с индексом i элементу с индексом j. Если они равны, это означает, что мы нашли дубликат.
• System.out.println("Duplicate found: " + numbers[j]);: Если найден дубликат, эта строка выводит сообщение, указывающее на дублирующий элемент.

Сохраните файл, нажав Ctrl + S (или Cmd + S на macOS).

Теперь откройте терминал в нижней части WebIDE. Убедитесь, что вы находитесь в каталоге ~/project. Вы можете это проверить, введя pwd и нажав Enter. Вывод должен быть /home/labex/project.

Скомпилируйте Java-код с использованием команды javac:

javac FindDuplicatesNested.java

Если нет ошибок, компиляция будет успешной, и в каталоге ~/project будет создан файл FindDuplicatesNested.class. Вы можете проверить это, введя ls и нажав Enter.

Наконец, запустите скомпилированную Java-программу с использованием команды java:

java FindDuplicatesNested

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

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

Эффективная проверка на дубликаты с использованием HashSet

На предыдущем этапе мы использовали вложенные циклы для поиска дубликатов, что просто, но может быть медленно для больших массивов. На этом этапе мы научимся более эффективному способу поиска дубликатов с использованием HashSet.

HashSet - это коллекция в Java, которая хранит уникальные элементы. Это означает, что если вы попытаетесь добавить элемент, который уже находится в HashSet, операция добавления завершится неудачей (точнее, вернет false). Мы можем использовать это свойство для эффективного обнаружения дубликатов.

Вот идея: мы проходим по массиву, и для каждого элемента пытаемся добавить его в HashSet. Если метод add() возвращает false, это означает, что элемент уже есть в наборе, и, следовательно, он является дубликатом.

Создадим новый Java-файл с именем FindDuplicatesHashSet.java в каталоге ~/project.

Откройте файл FindDuplicatesHashSet.java в редакторе кода и добавьте следующий Java-код:

import java.util.HashSet;
import java.util.Set;

public class FindDuplicatesHashSet {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // Create a HashSet to store unique elements
        Set<Integer> uniqueElements = new HashSet<>();

        System.out.println("Finding duplicate elements using HashSet:");

        // Iterate through the array
        for (int number : numbers) {
            // Try to add the element to the HashSet
            // If add() returns false, the element is a duplicate
            if (!uniqueElements.add(number)) {
                System.out.println("Duplicate found: " + number);
            }
        }
    }
}

Рассмотрим новые части этого кода:

• import java.util.HashSet; и import java.util.Set;: Эти строки импортируют необходимые классы для использования HashSet.
• Set<Integer> uniqueElements = new HashSet<>();: Эта строка создает пустой HashSet, который будет хранить объекты Integer. Мы используем Set в качестве типа, потому что HashSet реализует интерфейс Set.
• for (int number : numbers): Это расширенный цикл for (также известный как цикл for-each), который представляет собой удобный способ пройти по каждому элементу массива numbers.
• !uniqueElements.add(number): Это основная логика. uniqueElements.add(number) пытается добавить текущий number в HashSet. Если число уже присутствует, add() возвращает false. Оператор ! инвертирует этот результат, поэтому условие if истинно только тогда, когда add() возвращает false, что указывает на дубликат.

Сохраните файл (Ctrl + S или Cmd + S).

Теперь скомпилируйте Java-код в терминале:

javac FindDuplicatesHashSet.java

Если компиляция прошла успешно, запустите программу:

java FindDuplicatesHashSet

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

Тестирование с отсортированным массивом

На этом последнем этапе мы рассмотрим другой подход к поиску дубликатов, особенно когда массив отсортирован. Если массив отсортирован, дубликаты всегда будут соседними элементами. Это позволяет очень просто и эффективно находить дубликаты, сравнивая только соседние элементы.

Сначала создадим новый Java-файл с именем FindDuplicatesSorted.java в каталоге ~/project.

Откройте файл FindDuplicatesSorted.java в редакторе кода и добавьте следующий Java-код:

import java.util.Arrays;

public class FindDuplicatesSorted {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // First, sort the array
        Arrays.sort(numbers);

        System.out.println("Finding duplicate elements in a sorted array:");

        // Iterate through the sorted array and compare adjacent elements
        for (int i = 0; i < numbers.length - 1; i++) {
            // If the current element is equal to the next element, it's a duplicate
            if (numbers[i] == numbers[i + 1]) {
                System.out.println("Duplicate found: " + numbers[i]);
            }
        }
    }
}

Рассмотрим ключевые части этого кода:

• import java.util.Arrays;: Эта строка импортирует класс Arrays, который предоставляет вспомогательные методы для работы с массивами, в том числе сортировки.
• Arrays.sort(numbers);: Эта строка сортирует массив numbers в порядке возрастания.
• for (int i = 0; i < numbers.length - 1; i++): Этот цикл проходит по отсортированному массиву. Мы проходим до numbers.length - 1, потому что сравниваем текущий элемент (numbers[i]) с следующим элементом (numbers[i + 1]).
• if (numbers[i] == numbers[i + 1]): Это условие проверяет, равен ли текущий элемент следующему элементу. Если они одинаковы, это означает, что мы нашли дубликат.

Сохраните файл (Ctrl + S или Cmd + S).

Теперь скомпилируйте Java-код в терминале:

javac FindDuplicatesSorted.java

Если компиляция прошла успешно, запустите программу:

java FindDuplicatesSorted

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

Этот метод очень эффективен для отсортированных массивов, так как требует только одного прохода по массиву после сортировки. Однако сама начальная сортировка имеет временную стоимость, которая зависит от алгоритма сортировки, используемого методом Arrays.sort(). Для примитивных типов, таких как int, метод Arrays.sort() в Java использует двухосевой быстрый алгоритм сортировки (dual - pivot quicksort), который имеет среднюю временную сложность O(n log n).

Теперь вы рассмотрели три разных способа поиска дубликатов в массиве на Java: с использованием вложенных циклов, с использованием HashSet и с использованием отсортированного массива. Каждый метод имеет свои компромиссы в плане простоты, эффективности и требований (например, отсортированность массива). Понимание этих разных подходов ценно для выбора наиболее подходящего метода для данной задачи.

Резюме

В этом практическом занятии (lab) мы рассмотрели различные методы проверки наличия дубликатов в массиве на Java. Мы начали с реализации простого подхода с использованием вложенных циклов, который заключается в сравнении каждого элемента с каждым другим элементом массива. Этот метод, хотя и прост в понимании, имеет временную сложность O(n^2), что делает его менее эффективным для больших массивов.

Затем мы научились использовать структуру данных HashSet для более эффективной проверки на дубликаты. Пройдя по массиву и попробовав добавить каждый элемент в HashSet, мы можем быстро определить, является ли элемент дубликатом, так как метод add() класса HashSet возвращает false, если элемент уже существует. Этот подход обеспечивает значительно улучшенную временную сложность, обычно O(n) в среднем. Наконец, мы рассмотрели, как предварительная сортировка массива также может быть использована для эффективного поиска дубликатов, так как после сортировки дубликаты будут соседними элементами.