Как очистить связанный список в $ mathcal {o} (n log n) $ времени?

Question

Мне было интересно, как удалить дублированные значения из связанного списка в $ mathcal {o} (n lg n) $ времени. У меня есть идея, что, используя сортировку слияния, когда мы хотим сравнить элементы для выбора маленького, если они равны на указателе и просто рассмотрим один элемент. Какие -нибудь альтернативы?

Answer 1

1. Сортируйте связанный список в $ O (N log n) $ времени.
2. Пройдите через каждый элемент списка в их порядке и удалите элемент, если он такой же, как предыдущий в $ O (n) $ времени.

Общая сложность - $ o (n log n) $, что вы ищете.

Answer 2

Вы можете сделать это в $ O (n) $ следующим образом.

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

2) Теперь пройдите хеш -таблицу и создайте новый связанный список, добавив узел для каждого найденного элемента. Это требует максимума $ O (n) $, поскольку хеш -таблица содержит не более $ N $ Elements, работа, выполненная на каждом элементе хэш -таблицы, составляет $ O (1) $, и добавление узла в новый список требует $ O (1) $.

Следовательно, общая сложность не более $ O (n) $.