题解 | #字符串排序#

字符串排序

http://www.nowcoder.com/practice/5190a1db6f4f4ddb92fd9c365c944584

题意

给定一行字符串, 要求对非字母固定位置不变, 字母按照字母序排序,同字母大小写保持原字符串中的顺序.

限制: 每组数据有多行字符串

方法

pair与内置排序

对于字母的部分, 构建 pair<小写字母,下标>,利用C++内部sort排序(pair先比较first后比较second)
最后按下标输出.

以样例数据为例

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

我们构建的pair 为

排序前
{a,0}
{f,2}
{a,3}
{m,4}
{o,5}
{u,6}
{s,7}
{s,9}
{a,10}
{y,11}
{i,12}
{n,13}
{g,14}
{m,17}
{u,18}
{c,19}
{h,20}
{a,22}
{d,23}
{o,24}
{a,26}
{b,27}
{o,28}
{u,29}
{t,30}
{n,32}
{o,33}
{t,34}
{h,35}
{i,36}
{n,37}
{g,38}

通过c++的sort排序

排序后
{a,0}
{a,3}
{a,10}
{a,22}
{a,26}
{b,27}
{c,19}
{d,23}
{f,2}
{g,14}
{g,38}
{h,20}
{h,35}
{i,12}
{i,36}
{m,4}
{m,17}
{n,13}
{n,32}
{n,37}
{o,5}
{o,24}
{o,28}
{o,33}
{s,7}
{s,9}
{t,30}
{t,34}
{u,6}
{u,18}
{u,29}
{y,11}

这样我们可以通过下标,知道原来的值, 而这个值是满足题意的(字母序,同字母按照原始字符串中顺序排列)

最后我们遍历位置,决定是字母从排序中的结果输出,还是非字母直接输出即可.

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)
int main(){
    string sline;
    while(getline(cin, sline)){
        const char *s = sline.c_str();
        int n = strlen(s);
        vector<pair<char,int> > chidx;
        rep(i,0,n){
            if(('a'<=s[i] && s[i]<='z') || ('A'<=s[i] && s[i]<='Z')){ // 是字母
                chidx.push_back({ 'a'<=s[i] && s[i] <='z'? s[i]:(s[i]-'A'+'a'),i}); // <小写,下标>
            }
        }
        sort(chidx.begin(),chidx.end()); // 排序
        int itr = 0; // 当前输出的字母的下标
        rep(i,0,n){
            if(!( ('a'<=s[i] && s[i]<='z') || ('A'<=s[i] && s[i]<='Z'))){ // 非字母
                printf("%c", s[i]);
            }else{ // 是字母
                printf("%c", s[chidx[itr++].second]);
            }
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 在读入,构建对,输出的部分,都是跟字符串长度相关,其中排序有额外耗时,所以总时间复杂度为 $O(n \cdot log(n))$

空间复杂度: 空间主要在两部分,一个是读入,一个是排序的vector,这两部分都是字符串的长度,所以总空间复杂度为 $O (n)$

按字母序进行枚举

首先我们把非字母的定位
枚举字母从a到z,并控制一个指向目标字符串空闲位置的下标
每次枚举,遍历原字符串,并在指向的下标处插值,这样就完成了排序

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)
char t[1010];
int main(){
    string sline;
    while(getline(cin, sline)){
        const char *s = sline.c_str();
        int n = strlen(s);
        rep(i,0,n){
            if(!( ('a'<=s[i] && s[i]<='z') || ('A'<=s[i] && s[i]<='Z'))){ // 固定非字母
                t[i] = s[i];
            }else{
                t[i] = 0;
            }
        }
        t[n] = 0;
        int itr = 0;
        rep(ch,'a','z'+1){ // 字母从a->z
            rep(i,0,n){ // 遍历字符串
                if(s[i] == ch || s[i] == ch-'a'+'A'){
                    while(t[itr] != 0)itr++; // 找到空白位置插入
                    t[itr] = s[i];
                    itr++;
                }
            }
        }
        printf("%s\n",t);
    }
    return 0;
}