题解 | #字符串排序#
字符串排序
http://www.nowcoder.com/practice/5190a1db6f4f4ddb92fd9c365c944584
c++map容器
算法思路
首先构造一个map<int ,vector>容器。然后按顺序遍历字符串，大写的字母以'A'为标准添加到对应下标的vector中；小写的字母以'a'为标准添加到对应下标的vector中；与此同时添加一个辅助队列添加对应的下标。之后将map中的字母按照下标（此时排好序）转成一维vector。最后将对应的字符串下标与排好序的字母序列一一对应
具体算法实现
using namespace std;
//获取字母并对其排序，以及存取其下标
typedef vector<char>V;
int main(){
string s;
getline(cin,s);
map<int,V>m;
//存取下标
vector<int>vi;
vector<char>vc;
for(int i=0;i<s.size();i++){
if(('a'<=s[i]&&s[i]<='z')){
m[s[i]-'a'].push_back(s[i]);
vi.push_back(i);
}if('A'<=s[i]&&s[i]<='Z'){
m[s[i]-'A'].push_back(s[i]);
vi.push_back(i);
}
}
//将二维数组转成一维
for(int i=0;i<26;i++){
for(int j=0;j<m[i].size();j++)vc.push_back(m[i][j]);
};
for(int i=0;i<vi.size();i++){
s[vi[i]]=vc[i];
}
cout<<s<<endl;
return 0;
}
