Обратный порядок слов - сложность времени?

Question

Входные данные: «Меня зовут Притам». Выходные данные: «Притамов зовут Меня».

Я уже писал об этом, но меня немного смущает сложность времени

public string ReverseWordsInAString(string str)
    {
        char[] temp = str.ToCharArray();
        int startIndex = 0;
        int endIndex = str.Length - 1;
        temp = ReverseString(temp, startIndex, endIndex);
        endIndex = 0;
        foreach (char c in temp)
        {
            if(c == ' ')
            {
                temp = ReverseString(temp, startIndex, endIndex-1);
                startIndex = endIndex + 1;
            }
            if (endIndex == str.Length-1)
            {
                temp = ReverseString(temp, startIndex, endIndex);
            }
            endIndex++;
        }
        str = new string(temp);
        return str;
    }

    public char[] ReverseString(char[] chr, int start, int end)
    {
        while (start < end)
        {
            char temp = chr[start];
            chr[start] = chr[end];
            chr[end] = temp;
            start++;
            end--;
        }
        return chr;
    }

Когда я вызываю метод ReverseString из цикла for, я думаю, что это больше не решение O (n).Пожалуйста, поправьте меня, если я ошибаюсь.У кого-нибудь есть лучшее решение.

Answer 1

Ваш код O(n). Вы можете убедиться в этом, посмотрев на число перестановок, в которых участвует каждый элемент, и равное 2 (один раз для начального обратного хода всей строки, второй для пословичного обращения). Кроме того, цикл foreach повторяется по каждому элементу ровно один раз.

Answer 2

на Java

String str= "My Name is Pritam";
String arr[] = str.split(" ");
for(int i = arr.length-1 ; i >=0 ; i--){
   System.out.println(arr[i]);
}

Answer 3

в рубине:

sentence = "My name is Pritam"
print sentence.split(" ").reverse.join(" ")

Answer 4

в Python,

sentence = "My name is Pritam"
' '.join(sentence.split(" ")[::-1])

Answer 5

Разделите строку и поместите ее в стек. Извлекайте элементы из стека и добавляйте их в новую строку. Требуется дополнительное пространство, но только что опубликовано, потому что это может быть простым способом реализации обратной строки

public class StringReverse {

public static void main (String args[]){

    String input = "My name is Pritam";

    Stack<String> stack  = new Stack<String>();

    String[] strings= input.split(" ");

    for(String str :strings){
        stack.push(str);
    }

    String reverse = "" ;

    while(!stack.isEmpty()){
        reverse = reverse + " " + stack.pop();
    }

    System.out.println(reverse);
}

}

Answer 6

Возможно, дубликат, я задал похожий вопрос некоторое время назад.Но ответы, которые я получил, были очень интересными, на самом деле это изменило способ, которым нужно думать о сложности;) .... Сложность времени

Answer 7

В С;

char *s = "My Name is Pritam", *t = s + strlen(s), *end = strchr(s,' ')-1;
while( t != end )
{
  *(t = strrchr(t,' ')) = '\0';
  printf( "%s ", --t+2 );
}
printf( "%s", s );