c++ - 在线性时间内将一个小的排序列表合并到一个更大的排序列表中的算法，没有重复项

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;
            }
        }
    }

给定输入:

列表 1 = [0 1 2 5 6]

列表 2 = [3 4 5 7]

list1 应该是:

列表 1 = [0 1 2 3 4 5 6 7]

有什么建议吗？

Answer 1

鉴于插入操作的复杂度为 O(1)，您可以在线性时间内进行就地合并，这通常适用于所有列表实现。

与您的解决方案没有太大区别。算法非常相似:

让我们使用以下符号:smaller list 是我们不改变的列表。 较大列表 是我们通过插入较小列表中的元素来改变的列表。

• 从两个指向每个列表开头的迭代器开始
• 如果两个迭代器的值相同，则递增较小列表的迭代器(跳过重复项)
• 如果较大列表的迭代器的值更大(或者我们到达了较大列表的末尾)，则在它之前插入较小列表的值，递增较小列表的迭代器
• 否则，递增较大列表的迭代器。
• 如果较小列表的迭代器到达末尾则终止循环。

代码如下:

#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;
        }
    }
}