题解 | 字符串排序

#include <cctype>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

struct CustomCompare {
    // 重载operator()
    bool operator()(const pair<char, int>& a, const pair<char, int>& b)const {
        // 先全部转小写
        char lhs = a.first;
        char rhs = b.first;
        if (a.first >= 'A' && a.first <= 'Z') {
            lhs = a.first + 32;
        }
        if (b.first >= 'A' && b.first <= 'Z') {
            rhs = b.first + 32;
        }
        if (lhs != rhs) {
            return lhs < rhs;
        } else {
            // 比较出现的顺序
            return a.second < b.second;
        }
    }
};
int main() {
    // HJ26字符串排序
    string str; // 从键盘输入一个字符串
    std::getline(cin, str);
    // 对字母进行排序，不区分大小写
    /**
     * 按照字母表中的顺序排序（不区分大小写）
     * 同一字母的大小写同时存在时，按照输入顺序排序
     * 非字母字符保持原来的位置不参与排序
     */
    /**
     * 解题思路：
     * 需要记录字符和其出现的位置，可用一个vector<pair{char,index}>进行存放字符和出现的位置
     */
    // 需要记录字符和其出现的位置，可用一个vector<pair{char,index}>进行存放字符和出现的位置
    vector<pair<char, int>> index;
    for (int i = 0; i < str.length(); ++i) {
        index.push_back({str[i], i});
    }
    // 将是字母字符的按照上面的规则进行排序
    // 将字母全部抽取出来
    multiset<pair<char, int>, CustomCompare>
    ch_index; // 需要对multiset中的进行模板特化
    for (auto &[ch, index1] : index) {
        if (isalpha(ch)) {
            // 是字母，插入到新的数组当中
            ch_index.insert({ch, index1});
        }
    }
    // 排完序之后，加上原本非字母字符进行输出
    string res = str; // 先复制一份
    auto it = ch_index.begin();
    for (int i = 0; i < res.length(); ++i) {
        if (isalpha(res[i])) {
            // 换成排好序的
            res[i] = it->first;
            ++it;
        }
    }
    cout << res << endl;
}