C++无序数组唯一化deduplicate算法，要求时间复杂度为O（nlogn）

Question

本题目是邓俊辉《数据结构C++版》的第2章课后题[11]题 c）。要求对无序向量进行去重复操作，书中源代码是：
template<typename T>
int Vector<T>::deduplicate()
{
int oldSize = _size; //_size是向量的长度
Rank i = 1; //Rank是向量的秩，类型为int
while(i < _size)
(find(_elem[i], 0, i) < 0) ? i++ : remove(i);
//find（）函数用来找出向量中秩在 [0，i) 范围内等于_elem[i] 的元素，返回该元素的秩，没找到时返回 -1。
return oldSize - _size;
}
现在要求升级该算法，使其时间复杂度降至O（nlogn）。
请高人指点一下具体的算法，并分析一下时间复杂度，谢谢。
两位回答的思路我之前考虑过，只是因为无序向量去重操作后向量应该还是保持原来无序的样子，如果先排序再去重，向量就和原来不同了。请问这个地方怎么解决？

Answer 1

先排序，复杂度为O(n log n)，然后去重，也就是去掉相邻的相同元素即可，复杂度O(n)，故总的复杂度为O(n log n)。

int a[10] = {***};
sort(&a[0], &a[10]);
int* b = unique(&a[0], &a[10]);
则*a, *(a+1)到*(b-1)为无重的元素。sort和unique均为STL的算法，头文件algorithm。

追问

请问如果想保证去重操作后向量维持原来的顺序，可以做到么？

追答

这是没有现成的东西可以用。你可以存储一个pair，一个是数据，一个是原始顺序，去重之后再按原始顺序排序就可以了，复杂度不变。

Answer 2

首先对该无需数组进行排序，可以采用快速排序时间复杂度为O(nlogn)，然后遍历排好序的数组，判断重复的数字肯定紧挨着。