频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
C++ 删除数组中重复元素的算法(map)
2017-12-06 10:29:59      个评论    来源:梁的博客  
收藏   我要投稿

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  

void inserttomap(int *a, int n,std::map &outmap);  
void sprintmap(std::map &coutmap);  
void main()  
{  
    int a[10] = { 1, 1, 2, 3, 4, 4, 5, 6, 6, 8 };  
    std::map resultmap;  
    inserttomap(a, 10, resultmap);  
    sprintmap(resultmap);  
    system("pause");  
}  
void inserttomap(int *a, int n, std::map &outmap)  
{  
    std::map testmap;  
    std::pair< std::map< int, int >::iterator, bool > ret;  
    for (int i = 0; i < n; i++)  
    {  
        ret = testmap.insert({ a[i], 1 });  
        if (!ret.second)  
        {  
            ++testmap[a[i]];  
        }  
    }  
    outmap = testmap;  
}  

void sprintmap(std::map &coutmap)  
{  
    auto map_it = coutmap.cbegin();  
    while (map_it!=coutmap.cend())  
    {  
                std::cout << "元素" << map_it->first << "出现的次数为"   
     << map_it->second <

2.开辟数组空间去重实现代码

和第三种方法类似,在此不在赘述;

3.不开辟数组空间去重代码

#include  
#include   
void removemultip(int *a, int n, int &cout);  

void main()  
{  
    int a[10] = { 1, 1, 2, 3, 4, 4, 5, 6, 6, 8 };  
 std::sort(&a[0], &a[9]+1);//数组排序  
    int scount;//过滤后数组的有效位长度  
    removemultip(a, 10, scount);  
    for (int i = 0; i <= scount; i++)  
        {  
        std::cout << a[i] << std::endl;  
        }  
    system("pause");  
}  
void removemultip(int *a, int n,int &cout)  
{  
    if (n <= 1)return;  
    int start = 0;//基准位置  
    int end = 1; //游标位置  
    while (end

四.思想总结

1.map容器去重的思想

借助map容器中不能插入重复key值的特性进行常数或者字符串数组去重,又借助map.insert函数的返回值的标识可以统计重复元素出现的个数(在统计一组数据中出现次数最多的元素非常有用);

2.不开辟数组空间去重的思想

在去重操作实施前要保证数据的有序性,然后通过两个指针在原数组上面进行剔除重复元素,最后截取数组,得到去重后的数组;


<2、使用C++的map容器遇到的bug(map/set iterator not dereferencable)>

map
>::iterator it = shotList.find  

(shotId);  

while (it != shotList.end() &&  
    it->first.find(string("shot") + id) != string::npos)  
{  
    if (it->second.first <= start && it->second.second >= start||  
    it->second.first <= end && it->second.second >= end)  
    {  
        shotResultList.push_back(it->first);  
    }  

    ++it;  
}  

注意

1、while中迭代器的终止条件it != shotList.end()

2、必须为++it,it++会报错。


<3.实例>

一.实例1——map+双重for循环格式

#include 
#include
using namespace std;

int main()
{
    int a[10]={1,3,5,3,2,7,2,6,4,1};
    int j=0;
    map n;
    pair::iterator,bool> ret;

    for(int i =0;i<10;i++)
    {
       ret = n.insert(pair(a[i],i));
       if(ret.second!=false)
           a[j++] = a[i];
    }

    for(int i=0;i

二.实例2——set格式

#include 
#include 

using std::cout;
using std::endl;
using std::set;

int main(int argc, char* argv[])
{
    int ia[]={1,3,2,4,3,2,4,3,2,2};
    set is(ia,ia+10);
    for (set::const_iterator c_i=is.begin();c_i!=is.end();++c_i)
        cout<<*c_i<
        
   
点击复制链接 与好友分享!回本站首页
相关TAG标签 C++ 数组 算法 map
上一篇:为什么C++运算符的重载只是符号而已?
下一篇:C++初学者必看的知识思维导图
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站