C++ 删除数组中重复元素的算法(map)
<1、数组去重>
一.问题描述
在实际编程中我们经常遇到“去掉重复数字”等类似的问题,也就是“Remove the duplicate”问题。例如在“建立某个统计样本时,要去掉重复的元素”。下面将给出这类问题的解决思路。
二.解决思路
解决上述问题基本上有三种思路:
第一种:使用map容器过滤掉重复元素(适用于整形数据、字符串等);
第二种:利用数组进行去重,首先对该组数据进行排序,然后从头遍历数组,判断当前位置的数据和下一个位置的数据是否重复,若不重复,添加下一位中的数据到过滤后的数组中,并把比较的基准数据设置为刚加入的这个数据,然后继续进行比较。若重复,则跳过该数据去比较后面的(也可以做字符串的比较),需要使用两个指针(一个基准指针,一个游标指针);
第三种:是对第二种方法的改进,第二种方法需要开辟新的空间存储过滤后的元素,此方法中不需要开辟空间,只需用数组中没有重复的元素把重复的元素覆盖,过程如下:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
1 |
2 |
3 |
3 |
3 |
4 |
(1)基准指针首先指向数组第0个位置,游标指针指向第1个位置,比较两指针所指向的数据是否相等,若相等,游标指针向后移一位,基准指针不动,再次比较;若不相等,游标指针所指向的数据复制到基准指针的下一位,基准指针和游标指针各自从当前位置向后移一位,再次比较;
(2)终止条件:游标指针超过数组的最后一位;
(3)当前基准指针之前的一段数组则为去重后的数组(包括基准指针所指向的元素);
三.代码实现
1.map容器去重实现代码
#include
#include