В общем, нет.Представьте себе список из N дубликатов.Вам придется выполнить N-1 удалений, следовательно, O (N).
Если вы укажете конкретную структуру данных с удалением элементов лучше, чем O (1), то для определенных видов входных данных может быть лучший способ.
Даже если вы можете эффективно удалить диапазон элементов в O (1), и потребуется O (1) время, чтобы найти дубликат - представьте список, где есть N / 2 пары дубликатов.Вам все равно придется выполнить поиск N / 2 и удалить диапазоны N / 2, оба из которых O (N).
(есть также некоторая двусмысленность, поскольку заголовок вопроса «удалить дубликаты»,но тело относится только к удалению одного диапазона)
Если список, полученный в результате вашей сортировки, имеет следующее представление - у каждого узла есть значение, и для него существует число вхождений, то удаление дубликатов для одного значения будет тривиальнымустановите счетчик в 1 для этого узла.(A skip list , вероятно, имеет аналогичные характеристики, при условии, что существует достойная среда для сбора мусора, в которой нет затрат на восстановление памяти), так что это будет O (1) для одного дублирования.Если вам нужно удалить из списка все дубликаты, это все равно будет O (N).