题目：3451.字符串排序II

编写一个程序，将输入字符串中的字符按如下规则排序。

  • 规则 1：英文字母从 A 到 Z 排列，不区分大小写。如，输入：Type 输出：epTy。
  • 规则 2：同一个英文字母的大小写同时存在时，按照输入顺序排列。如，输入：BabA 输出：aABb。
  • 规则 3：非英文字母的其它字符保持原来的位置。如，输入：By?e 输出：Be?y。

输入格式

输入包含多组测试数据。

每组数据占一行，包含一个字符串。

输出格式

每组数据输出一行结果，为按要求排序后的字符串。

数据范围

字符串长度不超过 10001000，
每个输入最多包含 100100 组数据。

输入样例：

1
A Famous Saying: Much Ado About Nothing (2012/8).

输出样例：

1
A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).

算法思路

本题为排序问题

根据题目要求，我们可以将字符分为两种：

  • 大/小写字母
  • 其他字符（包括空格）

对于大/小写字母：

由于题目要求目标字符串中，英文字母按字典序升序排列，即：

str = (a|A)*(b|B)*⋯\cdots*(z|Z)* (正则表达式)

所以，我们可以使用26个队列容器，分别对应(a|A)* ~ (z|Z)*，最终输出时上一个队列空了再输出下一个；而而在队列内部，由于规则2，则按照输入时的顺序存放即可。

对于其他字符：

由规则3得，每个非英文字母保持在它原来的位置

因此，我们可以使用一个和字符串长度相等的char型数组，下标为特殊字符再字符串中的位置，元素为特殊字符的值，而英文字母对应的下标处的元素值为’\0’（ASCII码为0）。

在输出时，先判断是否为其他字符，若是则直接输出char[i]并continue

代码示例

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010;

char special[N];

bool isLowerLetter(char c) {
    return c >= 'a' && c <= 'z';
}

bool isCapitalLetter(char c) {
    return c >= 'A' && c <= 'Z';
}

int main() {
    string str;
    while(getline(cin, str)) {
        queue<char> letters[26];
        memset(special, 0, sizeof(special));
        for(int i = 0; i < str.length(); i ++) {
            char c = str[i];
            if(isLowerLetter(c)) {
                letters[c - 'a'].push(c);
            } else if(isCapitalLetter(c)){
                letters[c - 'A'].push(c);
            } else {
                special[i] = c;
            }
        }
        int point = 0;  //指向letters;
        for(int i = 0; i < str.length(); i ++) {
            if(special[i] != '\0') printf("%c", special[i]);
            else {
                while(letters[point].empty()) point ++;
                char c = letters[point].front();
                letters[point].pop();
                printf("%c", c);
            }
        }
        puts("");
    }

    return 0;
}