前端之家

  1. 首页
  2. 问答

如何使向量的元素唯一?(删除不相邻的重复项)

• 问答

我有一个包含很少非相邻重复项的向量.

举一个简单的例子，考虑:

2 1 6 1 4 6 2 1 1

我试图通过删除不相邻的重复项并保持元素的顺序来使这个 vector 独一无二.

结果是:

2 1 6 4

我尝试的解决方案是:

  1. 插入 std::set 但这种方法的问题是它会扰乱元素的顺序.
  2. 使用 std::sort 和 std::unique 的组合.但同样的顺序问题.

  3. 手动消除重复:

  1. Inserting into a std::set but the problem with this approach is that it will disturb the order of elements.
  2. Use the combination of std::sort and std::unique. But again same order problem.

  3. Manual duplicate elimination:

    Define a temporary vector TempVector.
    for (each element in a vector)
    {
        if (the element does not exists in TempVector)
        {
            add to TempVector;
        }
    }
    swap orginial vector with TempVector.

我的问题是:

是否有任何 STL 算法可以从向量中删除不相邻的重复项?它的复杂程度如何?

fandongdong888 回答：如何使向量的元素唯一?(删除不相邻的重复项)

不使用临时 set 就可以做到这一点，但(可能)会损失一些性能:

template<class Iterator>
Iterator Unique(Iterator first, Iterator last)
{
    while (first != last)
    {
        Iterator next(first);
        last = std::remove(++next, last, *first);
        first = next;
    }

    return last;
}

用于:

vec.erase( Unique( vec.begin(), vec.end() ), vec.end() );

对于较小的数据集，实现的简单性和不需要额外的分配可能会抵消使用额外的set 理论上更高的复杂性.不过，使用具有代表性的输入进行测量是唯一确定的方法.

这篇关于如何使向量的元素唯一?(删除不相邻的重复项)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持前端之家！

本文链接：https://www.f2er.com/3186436.html

大家都在问