算法 – 有效地反转字符数组中的单词(而不是字符)的顺序

栏目: 编程工具 · 发布时间: 6年前

内容简介:http://stackoverflow.com/questions/47402/efficiently-reverse-the-order-of-the-words-not-characters-in-an-array-of-chara

给出一个形成一个单词句子的字符数组,给出一种有效的算法来反转单词(而不是字符)的顺序.

示例输入和输出:

>>> reverse_words("this is a string")
'string a is this'

它应该是O(N)时间,O(1)空格(split(),并且不允许推/堆栈).

这个难题取自 here .

C/C++中的解决方案:

void swap(char* str, int i, int j){
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length){
    for(int i=0; i<length/2; i++){
        swap(str, i, length-i-1);
    }
}
void reverse_words(char* str){
    int l = strlen(str);
    //Reverse string
    reverse_string(str,strlen(str));
    int p=0;
    //Find word boundaries and reverse word by word
    for(int i=0; i<l; i++){
        if(str[i] == ' '){
            reverse_string(&str[p], i-p);
            p=i+1;
        }
    }
    //Finally reverse the last word.
    reverse_string(&str[p], l-p);
}

这应该是O(n)在时间上和O(1)在空间.

编辑:清理一下

字符串的第一遍显然是O(n / 2)= O(n).第二遍是O(n个组合长度的所有字/ 2)= O(n n / 2)= O(n),这使得这是一个O(n)算法.

http://stackoverflow.com/questions/47402/efficiently-reverse-the-order-of-the-words-not-characters-in-an-array-of-chara


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

概率论基础教程

概率论基础教程

罗斯 / 赵选民 / 机械工业出版社 / 2006-4 / 42.00元

本书是一本概率论的入门教材,系统介绍了概率论的基础理论及应用,在取材、结构和写作方法等方面具有鲜明的特点。通过例题阐述概率论的基本概念与方法是本书的一大特色。作者独具匠心地选择和编排了大量例题与习题,这些内容约占全书的三分之二。通过这些例题和习题,读者可以了解概率论在各个领域的广泛应用,如基因、彩票、法庭判决、NBA选秀等。   本书系统介绍了概率论的基础理论及应用,主要内容包括组合......一起来看看 《概率论基础教程》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

SHA 加密
SHA 加密

SHA 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换