不排序删除vector的重复元素，请给一个思路

如题。如果用sort,unique,和erase，虽然可以实现，但是要先排序才能实现。现在要求不排序，大家有没有方法？

23 个解决方案

#1

建议用map替代vector

#2

这个标准算法库有实现

#3

遍历的同时生成个hash表，表中有的就标记第一空位，后面的补上空。

#4

标准算法库那个实现的？没有吧？

#5

这是金山公司的笔试题，感觉比较难。

#6

不排序但至少需要遍历一遍吧至少0(N)

#7

应该不算难吧，对每个vector元素计算hash值，映射成一个数组的下标值，该数组元素存放的是链表的头指针，逐个比较该链表的节点的值是否与vector的值相同，相同则丢弃，不同则比较下个节点，整个链表都不相同则插入到链表末尾，最后遍历数组中各个链表即可。

#8

vector导入set在倒回来，不知道行不行。

#9

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


using namespace std;


int main()
{
    int a[] = {1, 2, 1, 3, 2, 4, 5, 3, 6, 7, 5};
    vector<int> vi(a, a + sizeof(a) / sizeof(a[0]));
    set<int> si;
    vector<int>::iterator it;

    for (it = vi.begin(); it != vi.end();)
    {
        if (si.count(*it) == 0)
        {
            si.insert(*it);
            ++it;
        }
        else
            vi.erase(it);//这里删除it指向的元素
    }
 
    for (it = vi.begin(); it != vi.end(); ++it)
    {
        cout<<*it<<endl;
    }
    
    system("pause");
    return 0;
}

#10

有了的就做个记录。在后面的遍历中找到了就删除。

#11

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

using namespace std;

int main()
{
    int a[] = {1, 2, 1, 3, 2, 4, 5, 3, 6, 7, 5};
    vector<int> vi(a, a + sizeof(a) / sizeof(a[0]));
    set<int> si;
    vector<int>::iterator it;

    for (it = vi.begin(); it != vi.end();)
    {
        if (si.count(*it) == 0)//这里判断当前元素是否已经出现过，若没有出现过则将该元素保留，并做标记
        {
            si.insert(*it);
            ++it;
        }
        else//如果前面已经出现过，则删除当前元素
            vi.erase(it);//这里删除it指向的元素
    }
 
    for (it = vi.begin(); it != vi.end(); ++it)
    {
        cout<<*it<<endl;
    }
    
    system("pause");
    return 0;
}

#12

如果允许的话，这个最简单了吧
#include<iostream>
#include<vector>
#include<set>


using namespace std;


int main()
{
int a[] = {1, 2, 1, 3, 2, 4, 5, 3, 6, 7, 5};
vector<int> vi(a, a + sizeof(a) / sizeof(a[0]));

set<int> si(vi.begin(),vi.end());


vector<int> ival(si.begin(),si.end());

vector<int>::iterator vit;
for (vit = ival.begin(); vit != ival.end(); ++vit)
{
cout<<*vit<<endl;
}

return 0;
}

#13

方法多了，就怕你这不满意那不满意的。

#14

这接用set
但效率上可能没vector排序后unique高

#15

引用 13 楼 iambic 的回复:

方法多了，就怕你这不满意那不满意的。

对，两层循环遍历最简单。

#16

遍历一次vector，当迭代器处于某个位置时，用find查找begin()和该位置之间，看迭代器处的值是否出现，如果出现说明重复则删除该迭代器值，否则继续遍历

int main(){
    int k[] = {1,2,3,8,2,1,4,5,6,5,1,2,3,7,8,9};
    vector<int> vec(k,k+sizeof(k)/sizeof(int));
    vector<int>::iterator iter = vec.begin();

    while(iter != vec.end()){
        if(iter != find(vec.begin(),iter,*iter)){
            iter = vec.erase(iter);
            continue;
        }
        cout<<*iter<<" ";
        iter++;
    }
    cout<<endl;

    return 0;
}

#17

两次遍历毕竟是O(N*N)的算法。如果要求剔除重复元素后保持原来的元素的相对位置，可以再开一个伴随数组保存下标，排序时同时移动，剔除重复元素后再按下标排回来，还是O(logN *N)的复杂度。

#18

建一个哈希好了，遍历一次O（n）就可以解决了

1.凡事出现的元素，删除。
2.没有出现的元素，放入哈希列表之中

#19

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

template <class T>
struct DataWithIndex
{
	T* pData;
	size_t Index;
};

template <class T>
struct DataEqual
{
	bool operator()(const DataWithIndex<T>&lhs, const DataWithIndex<T>& rhs)
	{
		return *(lhs.pData) == *(rhs.pData);
	}
};

template <class T>
bool operator<(const DataWithIndex<T>&lhs, const DataWithIndex<T>& rhs)
{
	if(*(lhs.pData) < *(rhs.pData))
		return true;
	if(*(lhs.pData) == *(rhs.pData) && lhs.Index < rhs.Index)
		return true;
	return false;
}

template <class T>
struct IndexLess
{
	bool operator()(const DataWithIndex<T>&lhs, const DataWithIndex<T>& rhs)
	{
		return lhs.Index < rhs.Index;
	}
};

template <class T>
void RemoveDupInVector(vector<T>& data)
{
	vector<DataWithIndex<T> > dataWithIndex;
	dataWithIndex.resize(data.size() );
	for(size_t i=0; i<data.size(); ++i)
	{
		dataWithIndex[i].pData = &(data[i]);
		dataWithIndex[i].Index = i;
	}
	sort(dataWithIndex.begin(), dataWithIndex.end() );
	typename vector<DataWithIndex<T> >::iterator iterNewEnd;
	iterNewEnd = unique(dataWithIndex.begin(), dataWithIndex.end() , DataEqual<T>() );
	dataWithIndex.erase(iterNewEnd, dataWithIndex.end() );   
	sort(dataWithIndex.begin(), dataWithIndex.end(), IndexLess<T>() );
	{
		typename vector<DataWithIndex<T> >::reverse_iterator riter = dataWithIndex.rbegin() ;

		for(int i= data.size() -1 ;data.size() > dataWithIndex.size();--i)
		{
			if(i> (*riter).Index)
				data.erase(data.begin() + i);
			else
				++riter;
		}
	}
}

int main(){
    int k[] = {1,2,3,8,2,1,4,5,6,5,1,2,3,7,8,9};
    vector<int> vec(k,k+sizeof(k)/sizeof(int));
    vector<int>::iterator iter = vec.begin();

    RemoveDupInVector(vec);
/*    while(iter != vec.end()){
        if(iter != find(vec.begin(),iter,*iter)){
            iter = vec.erase(iter);
            continue;
        }
        iter++;
    }
*/    iter= vec.begin();
    while(iter != vec.end() )
	    cout << *iter++;
    cout<<endl;

    return 0;
}

#20

你再加个限制不允许比较，就更NB了

#21

先转换为list，用list快速稳定删除，再转换为vector。。。

#22

19楼的代码又整理了一下

void RemoveDupInVector(vector<T>& data)
{
	vector<DataWithIndex<T> > dataWithIndex;
	dataWithIndex.resize(data.size() );
	for(size_t i=0; i<data.size(); ++i)
	{
		dataWithIndex[i].pData = &(data[i]);
		dataWithIndex[i].Index = i;
	}
	sort(dataWithIndex.begin(), dataWithIndex.end() );
	typename vector<DataWithIndex<T> >::iterator iterNewEnd;
	iterNewEnd = unique(dataWithIndex.begin(), dataWithIndex.end() , DataEqual<T>() );
	dataWithIndex.erase(iterNewEnd, dataWithIndex.end() );   
	sort(dataWithIndex.begin(), dataWithIndex.end(), IndexLess<T>() );
	{
/*		typename vector<DataWithIndex<T> >::reverse_iterator riter = dataWithIndex.rbegin() ;
		for(int i= data.size() -1 ;data.size() > dataWithIndex.size();--i)
		{
			if(i> (*riter).Index)
				data.erase(data.begin() + i);
			else
				++riter;
		}
*/
		typename vector<DataWithIndex<T> >::iterator iter = dataWithIndex.begin();
		typename vector<T>::iterator iterData = data.begin();
		while(iter != dataWithIndex.end() )
		{
			*iterData = data[(*iter).Index];
			++iter;
			++iterData;
		}
		data.erase(iterData, data.end() );
	}
}

#23

谢谢大家。