题解 | 字符串排序

//统计问题，哈希表

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    vector<vector<char>> hash(26,vector<char>());//vector<char> 也可以用队列
    //用哈希表，但是哈希表存储的元素不是出现的频次，而是有顺序的字符

    string str;
    
    getline(cin,str);

    for(char ch:str){
        //int pos=(ch>='a'&&ch<='z')?(ch-'a'):(ch-'A') //要考虑非字母字符的情况

        if(ch>='a'&&ch<='z'){
            hash[ch-'a'].push_back(ch);
        }
        else if(ch>='A'&&ch<='Z'){
            hash[ch-'A'].push_back(ch);
        }
        else{
            continue;
        }
    }

    vector<char> res;
    int pos=0;
    for(char ch:str)
    {
        if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){
            if(!hash[pos].empty())
            {
                ch=hash[pos].front();
                hash[pos].erase(hash[pos].begin());
            }
            else {
                while(hash[pos].empty())//pos可能并不是连续的
                {
                    pos++;
                }
                //pos++;
                ch=hash[pos].front();
                hash[pos].erase(hash[pos].begin());
            }


            res.push_back(ch);
        }
        else {
            res.push_back(ch);
        }

    }

    for(char ch:res){
        cout<<ch;
    }
    cout<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")