空格替换引申出的不同算法效率问题

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

在原来的字符串上替换，并保证输入的字符串后面有足够的空余内存。

思路：

解法一：最容易想到的就是当遇到空格时，将后面的字符向后面移动2位。此方法的时间复杂度为O(N^2)。

解法二：

　　首先遍历字符串，统计字符串中的空格数目，计算新的字符长度 newLen = oldLen + 2 * 空格数；

　　依次从字符串后面开始复制，分别用p1,p2指向旧新字符串的末尾，当遇到空格时，依次赋值‘0’，‘2’，‘%’；当p1 == p2时，过程终止(p1,p2之前的都是相同的，不用再复制)。此方法时间复杂度为O(N)。