设计时间复杂度小的算法

74 阅读 0 评论 49 点赞

我是靠谱客的博主真实发箍，最近开发中收集的这篇文章主要介绍设计时间复杂度小的算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

题目来自剑指offer

1.时间复杂度度为O(n^2)的算法

//length为牛客系统规定字符串输出的最大长度，固定为一个常数
class Solution {
public:
	void replaceSpace(char *str,int length) {
        int i=0;
        int k;
        while(i<length)
            {
                if(str[i]==' ')    
                {
                    for(k=length-1;k>i;k--)  //对含有 n 个空格是字符而言，最后一个空格后面的字符需要移动 n*n 次；O(n^2);
                        str[k+2]=str[k];
                    str[i]='%';
                    str[i+1]='2';
                    str[i+2]='2';
                    length+=2;
                    i+=2;
                }
        }
	}
};

2.时间复杂度度为O(n)的算法

先遍历一遍字符串，统计出总共有多少个空格

//length为牛客系统规定字符串输出的最大长度，固定为一个常数
class Solution {
public:
	void replaceSpace(char *str,int length) {
        int i,n;
        n=0;
        for(i=0;i<length;i++)
            if(str[i]==' ')    n++;
            
        char *p1,*p2;      //设置两个指针，p1指向原字符串的最后一个字符，p2指向替换之后字符串的最后一位；
        p1=&str[length-1];
        p2=p1+2*n;
        for(i=0;i<length;i++)
         {
            if(*p1==' ')
                {
                *p2='0';
                *(--p2)='2';
                *(--p2)='%';
            }
            else  *p2=*p1;
            p1--;p2--;                      //所有字符都只移动一次；
        }
	}
};