内容简介: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
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。