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

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

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

问题

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

思路

C++中,vector按先后顺序存储数据,因此可把没重复的字符串按顺序存到vector中。 map默认是按key从小到大的顺序存放数据,所以可把有重复的数据存到map中,并且以出现次数为key,以字符串为value

代码

代码语言:javascript
复制
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define len 8
// 计算某个字符串在数组中出现的次数
int countInArray(string s[], string element)
{
    int cnt = 0;
    for(int i = 0; i < len; i++)
    {
        if(element == s[i])
        {
            cnt++;
        }
    }
    return cnt;
}
int main()
{
    string s[len] = {"Liu Yi", "Chen Er", "Zhang San", "Chen Er", "Chen Er", "Li Si", "Li Si", "Wang Wu"};
    vector<string> v;
    map<int, string> m;
    for(int i = 0; i < len; i++)
    {
       int count = countInArray(s, s[i]);
       if(1 == count)
       {
           // 如果只出现一次,按先后顺序放到vector中
           v.push_back(s[i]);
       }
       else
       {
           // 出现多次的,放到map中,以次数为key,字符串为value
           m[count] = s[i];
       }
    }
    // 把map中的字符串,按出现次数从少到多的顺序,加到vector中
    map<int, string>::iterator mIt;
    for(mIt = m.begin(); mIt != m.end(); mIt++)
    {
        v.push_back(mIt->second);
    }
    vector<string>::iterator vIt;
    for(vIt = v.begin(); vIt != v.end(); vIt++)
    {
        cout << *vIt << endl;
    }
    return 0;
}

运行结果:

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

效率:

这个算法的时间复杂度是n ^ n + 2 * n, 你有更好的方法吗?

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

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

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

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

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