题解 | #字符串排序#

字符串排序

http://www.nowcoder.com/practice/5190a1db6f4f4ddb92fd9c365c944584

多多少少咱也击败了75+%的内存选手和20%的时间选手是不是

#include <cctype>
#include <string>
#include <vector>
#include <unordered_map>
#include <map>
using namespace std;

int id_get(char c)
{
    c=tolower(c);
    return c-'a';
}

int main()
{
    string s,ori;
    getline(cin,s);
    ori=s;
    unordered_map<int,bool> un_map;
    int pos=0;
    for(auto i:s)//对非字母进行标志为1
    {
        if(isalpha(i))
        {
            un_map.insert({pos,false});
           
        }
        else{
            un_map.insert({pos,true});
        }
         pos++;
    }
    
        for(auto it=s.begin();it!=s.end();)//s已经纯净化没有其他字符
    {
        if(!isalpha(*it))
        {
            it=s.erase(it);
        }
            else{
                it++;
            }
    }
    
//     for(int i=0;i<pos;i++)
//     {
//         cout<<un_map[i];
//     }
    
//     cout<<endl;

    
    unordered_map<char,int> alpha_num;//计算字符出现频率
    for(char c:s)
    {
        c=tolower(c);
        alpha_num[c]++;
    }
    
    vector<char> res;
    
    for(int i=0;i<26;i++)//字母按照顺序输出  从a开始遍历
    {
        char c='a'+i;
        int alplit_num=alpha_num[c];
        int ppos=0;
        for(int j=0;j<alplit_num;j++)//根据统计的个数依次查找
        {
            
            for(;ppos<s.size();ppos++)//查找
            {
                if(id_get(s[ppos])==i)
                {
                    res.push_back(s[ppos]);
                    continue;
                }
            }
            
        }
    }
    
//     cout<<s<<endl;
    auto it=res.begin();//输出结果
    for(int i=0;i<un_map.size();i++)
    {
        if(un_map[i]==false)
        {
            cout<<*it;
            it++;
        }
        if(un_map[i]==true)
        {
            cout<<ori[i];
        }
    }
    

    return 0;
}
全部评论

相关推荐

头像
11-26 15:46
已编辑
中南大学 后端
字节国际 电商后端 24k-35k
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务