给定一个字符串里面只有"R" "G" "B" 三个字符，请排序，最终结果的顺序是R在前 G中 B在后。 要求：空间复杂度是O(1)，且只能遍历一次字符串。

题目：给定一个字符串里面只有"R" "G" "B" 三个字符，请排序，最终结果的顺序是R在前 G中 B在后。 要求：空间复杂度是O(1)，且只能遍历一次字符串。

解析：本题的解法类似于快速排序partition算法，对于字符串str，利用两个下标start1,end1,start1初始时指向字符串的头部，end1初始时指向字符串的尾部，当str[start1]!='R'，str[end1]!='B'时候，不能简单像原来的partition那样直接作交换，而是要根据不同的情况做不同的处理，因为字符串中还包含第三类字符'G'。

C ++代码如下：

#include<iostream>#include<cstring>using namespace std;const int MAXLEN=100;//字符串的最大长度void Set_RGB(char *str);//位置调整函数，借助了快排的partition函数思想int main(){char str[MAXLEN+1];cin>>str;//输入只包含'R','G','B'的字符串Set_RGB(str);cout<<str<<endl;//输出调整过的字符串return 0;}void Set_RGB(char *str){if(str==NULL)return;int len=strlen(str);int start1,end1,start2,end2;char tmp;start1=start2=0;end1=end2=len-1;while(true){while(str[start1]=='R'&&start1<=end1){start1++;if(start1>start2)start2=start1;//保证start2始终等于或大于start1}while(str[end1]=='B'){end1--;if(end1<end2)end2=end1;//保证end2始终等于或小于end1}if(start1>end1)break;if(str[start1]=='B'&&str[end1]=='R')//直接交换{tmp=str[start1];str[start1]=str[end1];str[end1]=tmp;}else if(str[start1]=='G'&&str[end1]=='R')  {//先交换tmp=str[start1];str[start1]=str[end1];str[end1]=tmp;while(end2>start2)//然后用end2向前扫描知道遇到第一个不是'G'的字符{if(str[end2]!='G')break;end2--;}if(start2<end2)//若start2<end2，则end2和end1位置的字符交换{tmp=str[end2];str[end2]=str[end1];str[end1]=tmp;}}else if(str[start1]=='B'&&str[end1]=='G'){//先交换tmp=str[start1];str[start1]=str[end1];str[end1]=tmp;while(start2<end2)//然后用start2向前扫描知道遇到第一个不是'G'的字符{if(str[start2]!='G')break;start2++;}if(start2<end2)//若start2<end2，则start2和start1位置的字符交换{tmp=str[start2];str[start2]=str[start1];str[start1]=tmp;}}else{while(start2<=end2)//分别用start2和end2从前，从后，向后，向前扫描第一个不是'G'的字符{if(str[start2]!='G'&&str[end2]!='G')break;if(str[start2]=='G')start2++;if(str[end2]=='G')end2--;}if(start2==end2&&str[start2]=='R')//若两下标相遇，并且是字符'R'，则和start1位置'G'的字符交换{tmp=str[start2];str[start2]=str[start1];str[start1]=tmp;}if(start2==end2&&str[end2]=='B')//若两下标相遇，并且是字符'B'，则和end1位置'G'的字符交换{tmp=str[end2];str[end2]=str[end1];str[end1]=tmp;}if(start2<end2)//若两下标相遇，分别交换start1与start2,end1与end2位置的字符{tmp=str[end2];str[end2]=str[end1];str[end1]=tmp;tmp=str[start2];str[start2]=str[start1];str[start1]=tmp;}}if(start2>=end2)//若start2与end2相遇，则扫描结束，保证扫描字符串一遍，因为扫描过程中start2始终在start1后面,end2始终在end1前面，break;}}

3楼jirongzi_cs2011昨天 17:21

若有问题，欢迎大家指出来，大家共同讨论学习。

2楼crush_on昨天 15:37

遍历数组获得 R，G，B的个数，然后根据个数对原数组进行赋值，虽然这样做不到只遍历一遍，但是时间复杂度和空间复杂度都会比较低吧

Re: jirongzi_cs2011昨天 17:12

回复crush_onn是的，时间复杂度是线性的，但是如果本题的难点在于，要求只遍历一次字符数组，如果没有这个要求的话，你的方法是个不错的解法

1楼lxgwm2008昨天 12:14

[code=cpp]nvoid sortRGB(char *_pRGB)n{ntint indexCurrent = 0;ntint indexG = -1;ntint indexB = -1;ntntif(0 == _pRGB){nttreturn;nt}nntwhile(_pRGB[indexCurrent]){nttswitch(_pRGB[indexCurrent]){ntttcase 'R':nttttif(indexG != -1 && indexB != -1){nttttt_pRGB[indexG++] = 'R';nttttt_pRGB[indexB++] = 'G';nttttt_pRGB[indexCurrent] = 'B';ntttt}else if(indexG != -1 && indexB == -1){nttttt_pRGB[indexG++] = 'R';nttttt_pRGB[indexCurrent] = 'G';ntttt}else if(indexG == -1 && indexB != -1){nttttt_pRGB[indexB++] = 'R';nttttt_pRGB[indexCurrent] = 'B';ntttt}else{nttttt//todontttt}nttttbreak;ntttcase 'G':nttttif(indexB != -1){nttttt_pRGB[indexB++] = 'G';nttttt_pRGB[indexCurrent] = 'B';ntttt}nttttif(-1 == indexG){ntttttindexG = indexCurrent;ntttt}nttttbreak;ntttcase 'B':nttttif(-1 == indexB){ntttttindexB = indexCurrent;ntttt}nttttbreak;ntttdefault:nttttfprintf(stdout, "Invalid parameter: %c\n", *_pRGB);nttttbreak;ntt}ntt++indexCurrent;nt}n}n[/code]n我也写了一个，还没验证。

Re: jirongzi_cs2011昨天 15:30

回复lxgwm2008n说说你考虑这个问题的的出发点吧