前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >按出现次数从少到多的顺序输出数组中的字符串(纠正)

按出现次数从少到多的顺序输出数组中的字符串(纠正)

作者头像
海天一树
发布2018-04-17 11:04:25
2.1K0
发布2018-04-17 11:04:25
举报
文章被收录于专栏:海天一树

问题

有一个数组为{"Liu Yi", "Chen Er", "Zhang San", "Chen Er", "Chen Er", "Li Si", "Li Si", "Wang Wu"}, 要求: (1)把数组中没重复的字符串按原先的先后顺序打印出来 (2)把数组中有重复的字符串,按出现次数从少到多的顺序打印出来,每个字符串只打印一次

思路

把字符串作为key、出现次数作为value,存到map中; 再把第一个map中的出现次数作为key、对应的字符串作为value,存到map<int, list 算法的时间复杂度为N。

代码

代码语言:javascript
复制
#include <iostream>
#include <map>
#include <list>
using namespace std;
#define len 8
int main()
{
    string s[len] = {"Liu Yi", "Chen Er", "Zhang San", "Chen Er", "Chen Er", "Li Si", "Li Si", "Wang Wu"};
    map<string, int> m;
    map<int, list<string> > m2;
    for(int i = 0; i < len; i++)
    {
        int cnt = 0;
        if(m.count(s[i]) > 0)
        {
            cnt = m[s[i]];
        }
        m[s[i]] = ++cnt;
        //把重复次数和list<string>存到另一个map中
        list<string> li;
        if(m2.count(cnt) > 0)
        {
            // 若key已经存在,则使用key所对应的list,而不是用新生成的list
            li = m2[cnt];
        }
        if(cnt > 1)
        {
            // 若重复次数从n变为n+1(这里n大于或等于1)
            // 要把元素从n所对应的list中移出,放到n+1所对应的list中
            list<string> oldList = m2[cnt - 1];
            oldList.remove(s[i]);
            m2[cnt - 1] = oldList;
        }
        li.push_back(s[i]);
        m2[cnt] = li;
    }
    map<int, list<string> >::iterator it;
    for(it = m2.begin(); it != m2.end(); it++)
    {
        int cnt2 = it->first;
        list<string> list2 = m2[cnt2];
        list<string>::iterator it2;
        for(it2 = list2.begin(); it2 != list2.end(); it2++)
        {
            cout << *it2 << endl;
        }
    }
    return 0;
}

运行结果:

代码语言:javascript
复制
Liu Yi
Zhang San
Wang Wu
Li Si
Chen Er

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-03-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 海天一树 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题
  • 思路
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档