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

Удаление дубликатов без сортировки: анализ подходов

Это отличный вопрос о выборе алгоритма и trade-offs. Многие считают, что для удаления дубликатов обязательна сортировка, но это НЕ всегда верно. Давайте разберём, почему я выбрал другой подход.

Подход 1: Сортировка + два указателя (классический)

ListInteger> removeDuplicates(List<Integer> list) {
    Collections.sort(list);  // O(n log n)
    List<Integer> result = new ArrayList<>();
    
    for (int i = 0; i < list.size(); i++) {
        if (i == 0 || !list.get(i).equals(list.get(i-1))) {
            result.add(list.get(i));
        }
    }
    return result;
}

Сложность: O(n log n) из-за сортировки Минус: модифицирует исходный список (побочный эффект)

Подход 2: HashSet (мой выбор)

List<Integer> removeDuplicates(List<Integer> list) {
    return new ArrayList<>(new LinkedHashSet<>(list));  // O(n)
}

Сложность: O(n) в среднем Преимущества:

• Скорость: в 2-3 раза быстрее сортировки на больших данных
• Сохранение порядка: LinkedHashSet сохраняет порядок вставки
• Простота: одна строка, понятно что происходит
• Предсказуемость: O(n) без худших случаев

Подход 3: Stream API (Java 8+)

List<Integer> removeDuplicates(List<Integer> list) {
    return list.stream()
        .distinct()
        .collect(Collectors.toList());
}

Плюсы: функциональный стиль, читаемо Минус: медленнее из-за overhead Stream API

Сравнение производительности

На листе из 1,000,000 элементов:

Когда сортировка действительно нужна?

// Если результат ДОЛЖЕН быть отсортирован
List<Integer> removeDuplicatesSorted(List<Integer> list) {
    return list.stream()
        .distinct()
        .sorted()
        .collect(Collectors.toList());
}

// Или если есть специальное требование
// например, работать с очень малым heap (O(1) дополнительная память)
// и исходный список уже отсортирован

Критерии выбора алгоритма

Используй HashSet если:

• Нужна максимальная скорость (O(n))
• Порядок элементов не критичен или нужно сохранить исходный
• Есть достаточно памяти
• Элементы hashable

Используй сортировку если:

• Результат ДОЛЖЕН быть отсортирован
• Очень ограничена память (O(log n) для сортировки)
• Элементы не имеют hashCode() (редко)

Используй Stream.distinct() если:

• Код входит в цепочку stream операций
• Читаемость важнее микро-оптимизаций

Вывод

Отсутствие сортировки — это обоснованное решение, потому что:

1. HashSet работает в O(n) вместо O(n log n)
2. Сохраняет исходный порядок
3. Не требует модификации исходного списка

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