算法(替换空格)

题目

请实现一个函数，把字符串中的每个空格替换成”%20”。例如输入“we are happy”，则输出“we%20are%20happy”，并且时间复杂度为O(n)

分析

第一种思路

首先看题目，替换的话很简单。从头开始遍历遇到空格就替换成”%20”,但是此时其他的字符串则要后移。如下图

这样的话也能实现替换的功能，但是时间复杂度为O(n²),显然这点不符合我们的要求。

第二种思路

我们前边的思路是从前往后移动，时间复杂度为O(n²)，但是如果我们从后往前移动呢？

相当于一前一后指针，指针p1和p2同时往前移动，并且将p1的内容复制到p2的位置上，遇到空格则p1停下，p2开始填充”%20”这三个字符，然后p2往前移动3个单位，此时p1、p2再次开始同时往前移动

代码

int findSpace(char string[]);

void replacewhiteSpace(char string[],int length){
    int countSpace = findSpace(string);
    int originLength = length;
    int replacedLength = originLength-countSpace+countSpace*3;
    int originIndex = originLength-1;
    int replacedIndex = replacedLength-1;
    string[replacedLength]='\0';
    while (originIndex>0) {
        if (string[originIndex]==' ') {
            string[replacedIndex]='0';
            string[replacedIndex-1]='2';
            string[replacedIndex-2]='%';
            replacedIndex = replacedIndex-3;
        }else{
            string[replacedIndex]=string[originIndex];
            --replacedIndex;
        }
        --originIndex;
    }
}
int findSpace(char string[]){
    int i = 0;
    int count = 0;
    while (string[i]!='\0') {
        if (string[i] == ' ') {
            count++;
        }
        i++;
    }
    return count;
}
//******* 测试数据 *********
//char string[] = "we are happy";
//replacewhiteSpace(string,sizeof(string)/sizeof(string[0]));