Можно ли придумать более оптимальный способ удаления дубликатов из массива

Что проверяют

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

Как отвечать

Идиоматичный ответ на C# короткий:

var unique = source.Distinct().ToArray();

Внутри Distinct держит хеш-множество, работает за O(n) в среднем, выполняется лениво и сохраняет порядок первого появления. Если порядок не важен и нужен сам набор, достаточно new HashSet<int>(source).

Дальше объясните, за счёт чего получается линейное время: хеш-таблица меняет перебор сравнений на вычисление хеша и обращение по корзине. Плата за это O(n) дополнительной памяти.

Полезно назвать альтернативы под условия задачи:

• массив отсортирован или его не жалко отсортировать: дубликаты снимаются проходом двух указателей на месте, O(n log n) по времени и O(1) по памяти;
• элементы ссылочного типа: нужен согласованный GetHashCode и Equals либо отдельный IEqualityComparer<T>, иначе сравнение пойдёт по ссылке;
• уникальность по одному полю, а вернуть надо объект целиком: подходит DistinctBy.

Где спотыкаются

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

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

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