题目描述：请实现一个函数，把字符串中的每个空格替换成“%20”。例如，输入“We are happy.”，则输出“We%20are%20happy.”。
看到这个题目的时候我们首先想到的是，从前向后遍历，每找到一个空格就把这个空格替换成%20，但是空格只有一个字符，%20 有三个字符，这样替换的时候势必要将数组中的元素向后移动。而且有些字符还被不止移动一次， 假设字符串长度是n，对每个空格字符，需要移动后面O(n)个字符，因此对于含有O(n)个空格字符的字符串而言，总的时间效率是O(nxn)，有没有时间复杂度不是这么高的方法呢？
时间复杂度为O(n)的解法： 1.首先确定我们的字符串中有多少个空格，每一个空格要替换成三个字符，则需要增加两个字符的空间，最后形成的字符串的大小就等于原来字符串的长度加上2乘以空格数目。则上例中最后字符串的长度是18. 2.准备连个指针，p1和p2。p1指向原始字符串的末尾，p2指向替换之后的字符串的末尾。 3.向前移动指针p1，逐个把它指向的字符复制到p2指向的位置，直到碰到第一个空格为止。如下图所示，阴影部分为复制过的字符。 4.直到遇到一个空格，p1向前移动1格，在p2之前插入字符串“%20”。p2向前移动三格。 5.同理替换其他的空格。
代码实现：
void ReplaceBlank(char* str, int length)//参数为需要改变的数组，这里默认这个数组中的空间是能够存储插入空格替换字符串的 { if(str == nullptr && length <= 0)//边界条件 return; int originalLength = 0;//字符串数组的原始长度 int numberOfBlank = 0;//字符串中空格的个数 int i = 0; while(str[i] != '\0') { ++ originalLength; if(str[i] == ' ') ++ numberOfBlank; ++ i; } int newLength = originalLength + numberOfBlank * 2;//新数组的长度 if(newLength < length) return; int indexOfOriginal = originalLength;//定义的两个指针分别指向的位置 int indexOfNew = newLength; while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal) { if(str[indexOfOriginal] == ' ') { str[indexOfNew --] = '0'; str[indexOfNew --] = '2'; str[indexOfNew --] = '%'; } else { str[indexOfNew --] = str[indexOfOriginal]; } -- indexOfOriginal; } for(int i=0;i<18;i++){ cout<<str[i]; } }相关题目： 有两个排序数组A1和A2，内存在A1的末尾有足够多的空余空间容纳A2。请实现一个函数，把A2中所有数字插入A1中，并且所有的数字是排序的。 可以考虑从后往前比较。
