public static void reverseWords(char[] message) {
reverseCharacters(message, 0, message.length - 1);
int currentWordStartIndex = 0;
for (int i = 0; i <= message.length; i++) {
if (i == message.length || message[i] == ' ') {
reverseCharacters(message, currentWordStartIndex, i - 1);
currentWordStartIndex = i + 1;
}
}
}
private static void reverseCharacters(char[] message, int leftIndex, int rightIndex) {
while (leftIndex < rightIndex) {
char temp = message[leftIndex];
message[leftIndex] = message[rightIndex];
message[rightIndex] = temp;
leftIndex++;
rightIndex--;
}
}
乍一看，这似乎具有O(n)的时间复杂度和O(1)的空间复杂度。作者也建议这样做。但是，函数reverseWords首先调用reverseCharacters，其时间复杂度为O(n)，空间复杂度为O(1)。
然后for循环将最多运行n次，并再次调用reverseCharacters，其中包含一个while循环，该循环也将运行n次。难道这并不意味着时间复杂度将为O(n ^ 2)吗？
辅助函数中的代码实际上是否已嵌入到reverseWord函数中，是否会改变空间或时间复杂度？
最佳答案
[..] for循环最多可运行n次
真正
[..]并再次调用reverseCharacters，其中包含一个while循环，该循环也将运行n次。
这不是真的。
当reverseCharacters遇到空格或字符串结尾时，将调用reverseWords。边界leftIndex和rightIndex指向单词的开头和结尾，并且不会遍历整个字符串。
因此，字符串中的每个字符都会被查看两次，就像O(n + n)就是O(n)一样。
例:
对于字符串abcd efg hijk，很明显reverseWords扫描了此字符串。
当看到空格或字符串结尾时，它将调用reverseCharacters。对于上面的字符串，这会发生3次-(a - d)，(e - g)和(h - k)。它将边界之间的字符反转。这些操作都是而不是 O(n)。