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