tips:本文章内容来自《程序员编程艺术:面试和算法心得》
给定一个字符串里面只有"R" "G" "B" 三个字符,请排序,最终结果的顺序是R在前 G中 B在后。
要求:空间复杂度是O(1),且只能遍历一次字符串。
只是需要用到三个指针:一个前指针begin,一个中指针current,一个后指针end,current指针遍历整个数组序列,当
current指针所指元素为0时,与begin指针所指的元素交换,而后current++,begin++ ;
current指针所指元素为1时,不做任何交换(即球不动),而后current++ ;
current指针所指元素为2时,与end指针所指的元素交换,而后,current指针不动,end-- 。
参考代码:
/**
*荷兰国旗问题
*/
void helanguoqi (char* str,unsigned long length){
if(NULL== str || 0== length)
return;
char* strBegin = str;
char* strCurrent = str;
char* strEnd = str+length-1;
while(strCurrent < strEnd) {
if('R' == *strCurrent) {
swap(*strBegin, *strCurrent);
strBegin++;
strCurrent++;//仔细想想为什么这里可以++
}elseif('G' == *strCurrent){
strCurrent++;
}else{
swap(*strCurrent, *strEnd);
strEnd--;
}