Напишите наиболее эффективную реализацию функции RemoveDuplication ()
поэтому я учусь, и у меня есть этот вопрос, напишите наиболее эффективную реализацию функции RemoveDuplication (), которая удаляет любое дублирование в списке. Предположим, что список отсортирован, но может иметь дублирование. Итак, если список изначально <2, 2, 5, 6, 6, 6, 9>, ваша функция должна сделать это <2, 5, 6, 9>.
код, о котором я подумал, чтобы удалить дубликаты, вот здесь, я хотел бы знать, есть ли более эффективные способы удаления дубликатов в списке
template <class T>
void DLList<T>:: RemoveDuplication()
{
for(DLLNode<T>*ptr = head; ptr!=NULL; ptr=ptr->next)
while (ptr->val == ptr->next->val)
{
ptr->next->next->prev = ptr;
ptr->next = ptr->next->next;
}
}
Решение
Похоже, ваш код будет работать в O (n), что хорошо для алгоритма. Это, вероятно, не будет более эффективным, потому что вам придется посетить каждый элемент, чтобы удалить его.
Если вы не хотите удалять дубликаты объектов, но хотите вернуть новый список содержащий неповторяющиеся объекты, вы можете сделать это немного быстрее, сделав его O (m), где m — количество уникальных чисел, которое меньше или равно n. Но я не мог придумать, как это сделать.
Подводя итог, можно быть немного быстрее, но это сложно, и улучшение незначительно.
пс. Не забудьте удалить материал, когда вы берете его из списка;)
Другие решения
Я думаю, что O (n) в порядке.
Однако самое главное, ваша программа потерпит крах 🙂
for(DLLNode<T>*ptr = head; ptr!=NULL; ptr=ptr->next)
while (ptr->val == ptr->next->val)
Код защищающий ptr->next не проверяя, что это != NULL,
Следовательно, алгоритм должен завершиться сбоем, когда он достигнет последнего элемента списка.
А теперь вопрос оптимизации: как сделать программу корректной, не проверяя ptr И ptr-> next на каждой итерации?