Алгоритм объединения небольшого отсортированного списка в больший отсортированный список без дубликатов за линейное время

Question

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

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

Вот функция, которая берет список и объединяет их, используя новый список "temp". Примечание: здесь используется пользовательский список, но вы можете предположить, что метод вставки работает так же в версии STL.

void mergeNoDups(const List<Object> & rhs)
    {
        List<int> temp;

        for (const_iterator iter = this->begin(), iter2 = rhs.begin(); iter != this->end() || iter2 != rhs.end();)
        {
            if((iter != end()) && iter2 == end() || (*iter < *iter2))
            {
                temp.push_back(*iter);
                ++iter;
            }
            else if (*iter == *iter2)
            {
                ++iter2;
            }
            else if (*iter > *iter2)
            {
                temp.push_back(*iter2);
                ++iter2;
            }
        }
    }

Заданные входные данные:

list1 = [0 1 2 5 6]

list2 = [3 4 5 7]

list1 должно быть:

list 1 = [0 1 2 34 5 6 7]

Любые советы?

Answer 1

Вы можете выполнить слияние на месте за линейное время, учитывая, что операция вставки имеет значение O (1), что обычно верно для всех реализаций списка.

В вашем решении нет большой разницы. Алгоритм очень похож:

Будем иметь следующую запись: меньший список - это список, который мы не изменяем. Большой список - это список, который мы изменяем, вставляя элементы из меньшего списка.

• Начнем с двух итераторов, указывающих на начало каждого списка
• Если значенияоба итератора одинаковы, инкрементный итератор меньшего списка (пропустить дубликаты)
• Если значение на итераторе большего списка больше (или мы достигли конца большего списка), вставьте значениеиз меньшего списка перед ним увеличить итератор меньшего списка
• В противном случае увеличить итератор большего списка.
• Завершить цикл, если итератор меньшего списка достиг конца.

Код ниже:

#include <list>

template<typename T>
void mergeNoDups(std::list<T>& larger, const std::list<T>& smaller)
{
    typename std::list<T>::iterator itl = larger.begin();
    typename std::list<T>::const_iterator its = smaller.begin();

    while (its != smaller.end())
    {
        if (itl == larger.end() || *itl > *its)
        {
            larger.insert(itl, *its);
            ++its;
        }
        else if (*itl == *its)
        {
            ++its;
        }
        else // *itl < *its
        {
            ++itl;
        }
    }
}