高效替换字符串中的空格

请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入"We are happy."，则输出"We%20are%20happy."。

看到题目之后的第一感觉

---

看到题目后，第一个想法是从头到尾扫描字符串，遇到一个空格，就把空格替换成%20，但是这样的话，偏后面的字符就没碰到一个空格，就要移动一次，如果字符串长度为n，那么移动一次的时间复杂度为O(n)，那么对于含有O(n)个空格字符的字符串而言的时间复杂度是O(n^2)。会不会有更快的方法？

时间复杂度为O(n)的方法

---

我们可以先遍历一次字符串，统计出空格的数量，还有非空格的数量，那么可以每有一个空格，则替换之后的字符串比原字符串多了两个字符，那么替换后的字符串长度为:非空格的数量+空格的数量*2。
这样在最后移动的时候，每个字符只需要移动一次。

实现方法

---

从字符串的后面开始复制和替换，定义两个指针P1,P2。P1指向原字符串的末尾，P2指向替换之后字符串的末尾。接下来向前移动P1,逐个把它的字符复制到P2指向的位置，直到碰到第一个空格为止。碰到空格之后，接下来的操作是:P1继续向前移动，P2则向前移动3格插入"%20"。若P1,P2指向同一位置，表明所有空格都已经替换完毕。

---

void ReplaceBlank(char string[],int length)//length为字符数组的总容量 { if(string==NULL||length>0) return; //originalLength为字符串string的实际长度 int numberOfBlank=0; int originalLength=0; int i=0; while(string[i]!='\0') { originalLength++; if(string[i]==' ') numberOfBlank++; i++; } //indexOfNew为把空格替换成"%20"之后的总长度 int indexOfNew=originalLength+numberOfBlank*2; if(indexOfNew>length) return; int indexOfOriginal=originalLength; while (indexOfNew>indexOfOriginal) { if(string[indexOfOriginal]!=' ') string[indexOfNew--]=string[indexOfOriginal]; else { string[indexOfNew--]='0'; string[indexOfNew--]='2'; string[indexOfNew--]='%'; } indexOfOriginal--; } }

---