При ожидаемом O(1) для операций hash set алгоритм работает за O(n) времени и использует O(k) дополнительной памяти. Это оценка при нормальном распределении хешей, не универсальный worst case.
Какова сложность удаления дублей через множество?
При ожидаемом O(1) для операций hash set алгоритм работает за O(n) времени и использует O(k) дополнительной памяти. Это оценка при нормальном распределении хешей, не универсальный worst case.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Алгоритм проходит массив из n целых чисел слева направо. Если число ещё не встречалось в hash set, добавляет его в множество и результат. Порядок первых вхождений сохраняется. Оцените время и дополнительную память, обозначив число разных значений через k.
Ответ
При ожидаемом O(1) для операций hash set алгоритм работает за O(n) времени и использует O(k) дополнительной памяти. Это оценка при нормальном распределении хешей, не универсальный worst case.
Каждый элемент проверяется один раз; добавлений в множество и результат не больше k. Для [3,1,3,2,1] получится [3,1,2]. При патологических коллизиях операции множества могут быть дороже и итоговая оценка зависит от реализации. Замена множества линейным поиском в уже собранном результате даёт до O(n²) сравнений. Если исходный порядок не важен, можно рассмотреть сортировку, но это другой контракт.