如何使向量的元素独特？ （删除不相邻的重复项） [英] How to make elements of vector unique? (remove non adjacent duplicates)

问题描述

我有一个包含很少不相邻的重复的向量。

I have a vector containing few non-adjacent duplicates.

作为一个简单的例子，请考虑：

As a simple example, consider:

2 1 6 1 4 6 2 1 1

尝试通过删除不相邻的重复项并维护元素的顺序使此向量是唯一的。

be：

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算法可以从向量中删除不相邻的重复项？它的复杂性是什么？

Is there any STL algorithm which can remove the non-adjacent duplicates from the vector ? what is its complexity?

推荐答案

我认为你会这样做：

我会在向量上使用两个迭代器：

I would use two iterators on the vector :

第一个读取数据并插入一个临时集。

The first of one reads the data and inserts it a temporary set.

当读取的数据不在集合中时，将其从第一个迭代器复制到第二个迭代器，并递增它。

When the read data was not in the set you copy it from the first iterator to the second and increment it.

只有第二个迭代器的数据。

At the end you keep only the data up to the second iterator.

复杂度是O（n .log（n）），因为重复元素的查找使用集合，而不是向量。

The complexity is O( n .log( n ) ) as the lookup for duplicated elements uses the set, not the vector.

#include <vector>
#include <set>
#include <iostream>

int main(int argc, char* argv[])
{
    std::vector< int > k ;

    k.push_back( 2 );
    k.push_back( 1 );
    k.push_back( 6 );
    k.push_back( 1 );
    k.push_back( 4 );
    k.push_back( 6 );
    k.push_back( 2 );
    k.push_back( 1 );
    k.push_back( 1 );

{
	std::vector< int >::iterator r , w ;

	std::set< int > tmpset ;

	for( r = k.begin() , w = k.begin() ; r != k.end() ; ++r )
	{
		if( tmpset.insert( *r ).second )
		{
			*w++ = *r ;
		}
	}

	k.erase( w , k.end() );
}


    {
    	std::vector< int >::iterator r ;

    	for( r = k.begin() ; r != k.end() ; ++r )
    	{
    		std::cout << *r << std::endl ;
    	}
    }
}

这篇关于如何使向量的元素独特？ （删除不相邻的重复项）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！