【例72.3】 提取数字串按数值排序

解题思路

逐字符扫描，遇数字开始累计一个整数，遇非数字就把已累计数入数组并复位。末尾补一个非数字哨兵保证最后一段也入库，再排序逗号输出。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

前导零按数值消失；重复数字串保留；没有数字输出0。

复杂度

总长L，数字段k，时间O(L+k log k)，空间O(L)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin, s);
    s += '#';
    vector<long long> a;
    long long value = 0;
    bool active = false;
    for (char c : s) {
        if (c >= '0' && c <= '9') {
            value = value * 10 + c - '0';
            active = true;
        } else if (active) {
            a.push_back(value);
            value = 0;
            active = false;
        }
    }
    sort(a.begin(), a.end());
    if (a.empty())
        cout << 0;
    else
        for (size_t i = 0; i < a.size(); i++) {
            if (i)
                cout << ",";
            cout << a[i];
        }
    cout << "\n";
    return 0;
}