颠倒单词的顺序——时间复杂度？

Question

输入：“我的名字是普里塔姆” 输出：“Pritam is Name My”

到目前为止我已经写了这个，但是我对时间复杂度有点困惑

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;
    }

当我从 for 循环调用 ReverseString 方法时，我认为它不再是 O(n) 解决方案。如果我错了，请纠正我。大家有没有更好的解决办法。

Answer 1

爪哇语

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 2

您的代码是O(n)。您可以通过查看每个元素涉及的交换次数来看到这一点，即 2（一次用于整个字符串的初始反转，第二次用于逐字反转）。此外，foreach 循环对每个元素精确地迭代一次。

Answer 3

在红宝石中：

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

Answer 4

在C中；

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 );

Answer 5

可能重复，我不久前曾问过类似的问题。但我收到的回复非常有趣，实际上它确实改变了对复杂性的思考方式;).... 时间复杂度

Answer 6

分割字符串并将其压入堆栈。从堆栈中弹出元素并将其添加到新字符串中。需要额外的空间，但只是发布，因为它可能是实现字符串反转的简单方法

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 7

在Python中，

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