学步园

题目：

乱序的数组中去除重复元素。数组元素类型不一定是int型。
要求时间复杂度：O(n).

 

思路：

 

利用STL中set的性质，set中不允许有重复的元素，故方法有：

 

第一种方法是利用
set的特性，set中不允许有相同的值，
所以利用set的构造将相同值清除，
再将set中的值赋值到数组中。

第二种方式是
1，利用vector,先排序，这样数组中相同的值就会靠在一起了。
2，使用unique_copy在复制时，会将靠在一起的相同的值简化为一个，这样复制到数组中当然就可以了。

 

源代码说明为：

 

#include <vector>
#include <set>
#include <algorithm>

//两个函数的参数及返回值意义相同
//参数:
// array: [in, out] 提供500个数的数组头指针，并且整理后的值也存放其中
// length:[in] 这个数组中要整理的元素个数，在这里是500
//返回值:
// 经过整理后的数组中的还剩元素的个数。

//方法一
template <typename T>
unsigned int MakeUniqueArray1(T* array, unsigned int length)
{
std::set <T> s(array, array + length);
std::copy(s.begin(), s.end(), array);
return s.size();
}

//方法二
template <typename T>
unsigned int MakeUniqueArray2(T* array, unsigned int length)
{
std::vector <T> v(array, array + length);
std::sort(v.begin(), v.end());
T* end = std::unique_copy(v.begin(), v.end(), array);
return end - array;
}

使用说明:

int main()
{
int array[500];
//.....在这里对这个数组中的元素赋值

unsigned int len = MakeUniqueArray1(array, 500);
for (unsigned int i = 0; i < len; i++)
std::cout < < array[i] < < std::endl();
std::cin.get();
}

 

 

本题的延伸可以想到，统计大型数据中的重复元素的个数，这个可以利用hash实现，具体hash相关的例子可以参考http://blog.csdn.net/v_JULY_v/article/details/6256463