Как вы будете удалять дубликаты нечетных номеров из связанного списка?

Question

Требования / ограничения:

1. удалить только дубликаты
2. сохранить одну копию
3. список изначально не отсортирован

Как это можно реализовать в C? (Алгоритм и / или код будет принята с благодарностью!)

Answer 1

Существует несколько различных способов обнаружения / удаления дубликатов:

Вложенные циклы

Примите следующее значение в последовательности, затем просканируйте до конца списка, чтобы увидеть, не произойдет ли это значение снова.,Это O (n ² ) - хотя я считаю, что границы можно утверждать ниже?- но реальная производительность может быть лучше, поскольку выполняется только сканирование от i до end (не 0 до end), и оно может прекратиться досрочно.Это не требует дополнительных данных помимо нескольких переменных.

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

Сортировка и фильтрация

Сортировка списка (сортировка слиянием может быть изменена для работы со связанными списками), а затем обнаружение дублированных значений (онибудет бок о бок сейчас).С хорошей сортировкой это O (n * lg (n)).Фаза сортировки обычно является / может быть разрушительной (например, у вас есть «одна копия»), но она была изменена; -)

Сканирование и ведение поиска

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

Для малых значений n big-O практически бесполезен; -)

Счастливое кодирование.

Answer 2

Я бы либо

• произвёл сортировку списка с последующим линейным сканированием для удаления дубликатов
• использовал алгоритм на основе вставки, который уже удаляет дубликаты при повторном построении списка

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

Answer 3

Если список очень длинный и вам нужны разумные показатели, и вы согласны с выделением дополнительного журнала (n) памяти, вы можете отсортировать в nlog (n), используя qsort или сортировку слиянием:

http://swiss -knife.blogspot.com / 2010/11 / sorting.html

Затем вы можете удалить дубликаты в n (всего: nlog (n) + n)

Если ваш список очень маленький, вы можете сделать так, как предлагает jswolf19, и получите: n (n-1) / 2 худшее.

Answer 4

Это, вероятно, самый неоптимизированный кусок дерьма, но он, вероятно, будет работать.

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

Answer 5

Ну, вы можете сначала отсортировать список, а затем проверить наличие дубликатов, или вы можете сделать одно из следующего:

for i from 0 to list.length-1
    for j from i+1 to list.length-1
        if list[i] == list[j]
            //delete one of them
        fi
    loop
loop

Answer 6

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

Вы хотите сканировать список последовательно.Каждый раз, когда вы сталкиваетесь с нечетным элементом, ищите его в своей хэш-таблице.Если этот номер уже есть в хеш-таблице, удалите его из списка, если не добавите его в хеш-таблицу, и продолжите.

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