题解 | #字符串排序#
字符串排序
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;
}