Можно ли удалить дубликаты из отсортированного списка менее чем за O (n) раз? - PullRequest
8 голосов
/ 11 ноября 2010

Я подозреваю, что есть способ, если вы можете сохранить, найдя другой конец диапазона повторяющихся значений быстрее, чем итерацией по этому подсписку

Ответы [ 4 ]

12 голосов
/ 11 ноября 2010

В общем, нет.Представьте себе список из 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).

3 голосов
/ 11 ноября 2010

В общем, нет, потому что вы всегда можете построить случай, когда у вас есть O (n) (список без дубликатов). Однако, если вы начнете делать предположения относительно данных (например, что существует не более log n различных элементов), вы можете получить что-то лучше (хотя я не уверен в этом конкретном случае).

Это, конечно, предполагает, что у вас есть какой-то способ эффективного «массового удаления», то есть вы можете удалить любой диапазон равных элементов в O (1) независимо от его размера.

1 голос
/ 11 ноября 2010

Не может быть

Что касается сравнения всех элементов с другими, нам нужно выполнить n * (n-1) = n2-n сравнений ... `

0 голосов
/ 11 ноября 2010

Я бы выбрал подход "бинарный поиск" для поиска концов диапазонов:

Предположим, у нас есть отсортированный список из n элементов.

  1. Сравните 1-й иn-й элемент - если он равен всему списку, является дубликатом.
  2. Выберите средний элемент (n / 2)
  3. Выполните рекурсивный поиск для двух подсписков.
...