题解 | #字符串排序#

#include <list>
#include<vector>
#include <iostream>
#include<string>
#include<algorithm>
#include<cctype>
#include<iterator>
using namespace std;

//链表挂着的哈希表，需要一次遍历原数组，一次遍历哈希表格即可；甚至不需要额外空间
int main() {
    string str;
    getline(cin,str);
    
    vector <list<int>> hash_vec(26);
 
    for(auto ch:str){
        if(isupper(ch))
            hash_vec[ch-'A'].push_back(1);
        else if(islower(ch))
            hash_vec[ch-'a'].push_back(0);
    }
    auto stb=str.begin();
    for(auto lst=hash_vec.begin(); lst!=hash_vec.end(); lst++){
        if (lst->empty()) continue;

        for(auto it:*lst){
            while(!isalpha(*stb) && stb != str.end())
                stb++;
            if(stb == str.end()) break; // 防止超出范围
            if(it)
                *stb='A'+(lst-hash_vec.begin());
            else
                *stb='a'+(lst-hash_vec.begin());
            stb++;
        }
    }

    cout<<str<<endl;
}
// 64 位输出请用 printf("%lld")