Как бы ты проверил наличие дубликатов в массиве из одного миллиона чисел?

Для проверки наличия дубликатов в массиве из одного миллиона чисел можно использовать несколько подходов:

1. Использование HashSet:
   • Пройти по массиву, добавляя каждый элемент в HashSet.
   • Если элемент уже есть в HashSet, значит найден дубликат.

import java.util.HashSet;

public boolean hasDuplicates(int[] arr) {
    HashSet<Integer> set = new HashSet<>();
    for (int num : arr) {
        if (!set.add(num)) {
            return true; // дубликат найден
        }
    }
    return false; // дубликатов нет
}

2. Сортировка массива:
   • Отсортировать массив.
   • Пройти по нему и проверить соседние элементы на равенство.

Этот способ требует O(n log n) времени на сортировку, а HashSet — в среднем O(n) по времени.

Для массива из миллиона элементов HashSet — оптимальный вариант по времени, при условии достаточной памяти.