c - 我的代码 : reversing words in a string? 的时间复杂度是多少 我应该考虑不对称间距吗？

Question

问题陈述:编写声明void str_words_in_rev(char *input, int length) 的函数，反转单词字符串中的单词。我已经为它实现了两种不同的解决方案，其中一种非常复杂。

解决方案 1: 我使用 void reverse(char* string, int start, int end) 函数反转整个字符串，该函数获取第一个和最后一个字母的索引要反转的字符串或子字符串。之后，我使用相同的反转函数反转字符串中的每个单词。

#include<stdio.h>

void swapChar(char *a, char *b) {
  char temp = *a;
  *a = *b;
  *b = temp;
}

int length(char *string) {
  if(string == NULL)
     return -1;
  int i=0;
  for(;string[i++];);
  return i;
}

void reverse(char* string, int start, int end) {
  int mid = start + (end - start + 1)/2;
  for(int i=start,j=end;i<mid;)
    swapChar(&string[i++], &string[j--]);
}

int main() {
  char str[] = "abc def ghij klmn";
  int i=0, j=0, len = length(str), flag = 0;

  if(str == NULL || !(*str))
     return 0;
  for(;str[j]!='\0';++j) {
     if(str[j] == ' ') {
       flag = 1;
       reverse(str,i,j-1);
       i = j+1;
     }
  }
  if(flag == 1) {
  reverse(str, i, j-1);
  reverse(str,0,len-2);
  }
  printf("%s\n", str);
  return 0;
}

解决方案 2:我使用 pushToEnd 函数将每个单词和后面的空格字符(在重新排列后)移到末尾，然后将末尾移到被推送的结束单词之前。如果我的解释不充分(对此我深表歉意)，可以注释掉一些 printf 语句以真正了解正在发生的事情。

        int pushToEnd(char *str, int length) {

        int len = 0;
        int i = 0, j = 0, k = 0, n = 0;
        for (i = 0; str[i++] != ' ' && i <= length;)
            ++len;
        if (len == length)
            return len;
        //printf("Length of first word:");
        //printf("%d\n", len);
        for (j = i - 1; j>0; --j)
            swapChar(&str[j], &str[j - 1]);
        ++len;
        //printf("After rearranging first word:");
        //printf("%s\n", str);
        //printf("Pushing first word toward the end\n");
        for (; k + 2 * len <= length; k = k + len) {
            for (int l = k; l<k + len; ++l) {
                swapChar(&str[l], &str[l + len]);
            }
            //printf("---%s---\n", str);
        }
        //printf("As blocks:");
        //printf("%s\n", str);
        //printf("K VALUE: %d\n", k);
        for (; k + len<length; ++k) {
            for (n = k + len; n>k; --n) {
                //printf("N VALUE: %d\n", n);
                swapChar(&str[n], &str[n - 1]);
            }
        }
        //printf("One by one:");
        //printf("%s\n", str);
        return len;
    }

    void str_words_in_rev1(char *input, int length){
    int len = 0;
    for (int end = length; end>0; end = end - len) {
        //printf("End:%d\n", end);
        len = pushToEnd(input, end);
    }
}

一旦您理解了问题陈述和我实现的解决方案，以下是我的问题:

我的解决方案的时间复杂度是多少？我认为第一个解决方案具有 O(n) 复杂性，第二个解决方案可能是 O(n^2) 但我不确定。

这两种解决方案都无法解释不对称间距。单词被颠倒了，间距也被颠倒了。在存在对称间距/多对称间距的情况下，它是难以察觉的。问题陈述对此并不清楚，但我想听听您对是否应该考虑它的看法。

Answer 1

解决方案 1 的时间复杂度为 O(N)。在哪里，
解决方案 2 是 O(kN)，其中 k 是字符串中的单词数，在最坏的情况下所有单词都是单个字符 O(N^2)。并且您逐字移动到最后并交换其他单词到前面，所以它是 O(kN)。