以O(N)时间复杂度和O(N)空间复杂度编写反转字符串程序

Question

我被要求解决以下问题：时间复杂度低于N^2，空间复杂度为O(N)：

编写程序来反转字符串：

输入：- "Hello World" 输出：- "olleH dlroW"

我已经尝试了很多方法，但无论我尝试什么，都无法得出比N^2更低的时间复杂度。我的代码如下所示，您有任何建议吗？如何提出具有线性时间复杂度的解决方案？

注意：不允许使用内置方法。

 public static String stringReverser(String str) {
        if (str == null || str.isEmpty()) {
            throw new IllegalArgumentException();
        }
        if (str.length() < 2) {
            return str;
        }
        String[] strArr = str.split(" ");
        StringBuffer newHolder = new StringBuffer();
        for (int i = 0; i < strArr.length; i++) {
            int j = 0;
            int len = strArr[i].length();
            char[] newCharStr = strArr[i].toCharArray();
            while (j < len) {
                char temp = newCharStr[j];
                newCharStr[j] = newCharStr[len - 1];
                newCharStr[len - 1] = temp;
                len--;
                j++;
            }
            newHolder.append(String.valueOf(newCharStr));
            if(i != strArr.length-1){
                newHolder.append(" ");
            }
        }

        return newHolder.toString();
    }

- Gökhan Akduğan

---

return new StringBuilder(str).reverse().toString(); - Elliott Frisch

这是一个算法问题，所以不允许使用内置方法。 - Gökhan Akduğan

Answer 1

看起来您想要翻转字符串中的单词，而不是整个字符串。这是您需要的：

public static String reverseWords(String str)
{
    char[] chars = str.toCharArray();
    int wstart=0;
    for (int pos=0;;pos++)
    {
        if (pos < chars.length && chars[pos]!=' ')
        {
            continue;
        }
        for (int wend=pos-1; wend>wstart; ++wstart,--wend)
        {
            char t=chars[wstart];
            chars[wstart]=chars[wend];
            chars[wend]=t;
        }
        if (pos>=chars.length)
        {
            break;
        }
        wstart=pos+1;
    }
    return String.valueOf(chars);
}

这是最快、最节省空间的版本。如果这是作业，您的教授会知道这不是您自己写的 :)

然而，你在问题中提到的那个版本符合要求——O(N)时间和O(N)空间——所以你可能想提交那个版本。恭喜！

既然您认为它需要O(N^2)的时间，那么下面是时间分解：

- str.split: O(输出数组大小+输出字符串大小)= O(str.length())，即O(N) - 迭代单词: O(单词数量) = O(N) - 创建和反转单词字符串: 每个单词的大小为O(size of word)，总共O(N) - newHolder.append: O(创建的字符串总大小) = O(str.length()) = O(N) - newHolder.toString(): O(输出的大小) = O(N)

因此，5*O(N) = O(N) —— 你做得很好。

- Matt Timmermans

Answer 2

以下算法使用O(n)的空间，精确地迭代输入字符串两次（我相信这满足时间复杂度）。一次迭代输入字符串是为了找到空格，另一次迭代是为了写出反转的单词。

算法大致如下：

• Find the first space (keep track of where the space is)
• Write the first word in reverse order (keep track of where the next word starts)

• Repeat until end of string

  public class ReverseEachWord {
  
  public static void main(String[] args) {
      String input = "Hello World";
      System.out.println(reverseEachWord(input));
  }
  
  public static String reverseEachWord(String input) {
  
      int len = input.length();
  
      char[] out = new char[len]; // O(n) space
      char[] in = input.toCharArray();
  
      int spacePos = 0;
      int activePos = 0;
  
      while (activePos < len) {
          spacePos = activePos+1;
          int spaceFound = -1;
          int offset = 0;
          while (spacePos < len) {
              if (in[spacePos] == ' ') {
                  out[spacePos] = ' ';
                  spaceFound = 0;
                  break;
              }
              spacePos++;
          }
          if (spaceFound < 0) {
              spacePos += spaceFound;
              offset = 1;
          }
  
          for (int i=0; i<(spacePos-activePos+offset); i++) {
              out[spacePos - i -1 - spaceFound] = in[i+activePos];
          }
          activePos = spacePos+1;
  
      }
  
      return Arrays.toString(out);
  }
  

  }

- Ian Mc

Answer 3

你正在使用split()，这会增加额外的O(N)时间复杂度。此外，你说不能使用内置方法！

以下是一个伪代码供你尝试。据我所知，它具有O(N)时间复杂度和仅O(N)空间复杂度。

i = 0, j = 0
for i = 0 to str.length:
    if str[i] == ' ':
        for k=i-1 to j:    // reverse looping
            print str[k]
        j = i + 1
// printing the last word
for k=i to j:
    print(s[k])

这是我对复杂度的直觉。外层循环需要O(N)，内层循环每个单词执行一次，因此再次需要O(N)，意味着总复杂度为O(N)。至于空间，如果你将字符存储在另一个数组中而不是打印出来，你需要一个大小为N的数组，其中N是源字符串的大小。因此，空间复杂度也是O(N)。

---

这是一个Java实现伪代码的示例：

：

public static String reverseIt(String str) {

    char[] source = str.toCharArray();
    char[] newArray = new char[source.length];

    int i = 0, j = 0, idx = 0;

    for(i = 0; i < source.length; i++) {
        if(source[i] == ' ') {
            for(int k = i-1; k >= j; k--, idx++) {
                newArray[idx] = source[k];
            }
            j = i + 1;
            newArray[idx++] = ' ';
        }
    }
    for(int k = i-1; k >= j; k--, idx++) {
        newArray[idx] = source[k];
    }

    return new String(newArray);
}

- Sнаđошƒаӽ

Answer 4

public String reverse(String str)
{
char [] chars= str.toCharArray();
int end=chars.length-1, half_len = (int) Math.ceil(chars.length/2);

for(int i=0;i<half_len;i++)
{
    if(chars[i]==' ')
    {
        continue;
    }
    else
    {
        char t=chars[i];
        chars[i]=chars[end];
        chars[end]=t;
    }
    end--;
}
}

易于理解 :)

- Jitesh Lakhwani