在线性时间内将一个小的排序列表合并成一个更大的排序列表的算法，没有重复。
我有两个不同数量的元素列表，每个列表至少包含一个重复的元素。我希望把较小的列表合并到更大的列表中，最坏的情况是线性时间。
我可以通过使用第三个临时列表来解决这个问题，但我特别需要将较小的列表合并为更大的列表，而不是创建第三个列表。
下面是一个函数，它接收一个列表并使用一个新的列表"temp“合并它们。注意:这使用了一个自定义列表，但是您可以假设insert方法在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应该是：
表1=0 1 2 3 4 5 6 7
有小费吗？
回答 1
Stack Overflow用户
发布于 2019-10-01 02:15:48
如果insert操作为O(1)，则可以在线性时间内进行就地合并，这对于所有列表实现来说都是正确的。
与你的解决方案没有太大的区别。算法非常相似：
让我们使用下面的表示法:较小的列表是我们不变异的列表。更大的列表是我们通过从较小的列表中插入元素来变异的列表。
如果两个迭代器的值相同，则两个迭代器首先指向每个列表的开头，如果两个迭代器的值相同，则为较小列表(跳过重复)的增量迭代器，如果较大列表的迭代器的值较大(或我们到达更大列表的末尾)，则增量迭代器，然后从前面的较小列表中插入值，如果较小列表的list
- Otherwise，增量迭代器到达终点，则增量迭代器对较大的list.
- Terminate循环的增量迭代器。
守则如下：
#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;
}
}
}https://stackoverflow.com/questions/58177029
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号