有效地扭转的话（不是字符）的顺序字符数组 [英] Efficiently reverse the order of the words (not characters) in an array of characters

问题描述

由于字符数组构成单词的句子，给出一个有效的算法来扭转它的话（不是字符）的顺序。

Given an array of characters which forms a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.

例输入和输出：

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

应该是O（N）的时间和O（1）空间（拆分（）及推/从堆栈弹出是不允许的）。

It should be O(N) time and O(1) space (split() and pushing on / popping off the stack are not allowed).

让人不解的是从这里

推荐答案

在C A液/ C ++：

A solution in 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）在空间（1）时间和O操作。

This should be O(n) in time and O(1) in space.

编辑：清理起来有点

第一传过来的字符串，显然是为O（n / 2）= O（N）。第二关是O（n +的所有文字/ 2合长度）= O（N + N / 2）= O（N），这使得这个一个O（n）的算法。

The first pass over the string is obviously O(n/2) = O(n). The second pass is O(n + combined length of all words / 2) = O(n + n/2) = O(n), which makes this an O(n) algorithm.

这篇关于有效地扭转的话（不是字符）的顺序字符数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！