Question

求解C语言基础题

使用线性表存储字符串 ，并设计一个算法，将字符串逆置，你只能使用O(1)的辅助空间。

Answer 1

按照你的要求编写的求出现最长的数字和位置的C语言程序如下

#include <stdio.h>

int main(){

 int a[]={1,1,2,2,2,3,3,3,3,5,5,6,6,6,6};

 int length=1,pos,i,j;

 for(i=1;i<sizeof(a)/sizeof(a[0]);i++){

  if(a[i]==a[i-length]){

   length++;

  }

 }

 printf("长度为%d\n",length);

 for(i=length-1;i<sizeof(a)/sizeof(a[0]);i++){

  if(a[i] == a[i-length+1]){

   for(j=i-length+1;j<=i;j++){

    if(j==i){

     printf("%d ",a[j]);

    }else{

     printf("%d,",a[j]);

    }

   }

   pos = i-length+1;

   printf("位置为%d\n",pos+1);

  }

 }

 return 0;

}

Answer 2

#include<stdio.h>

int main()

{ char c,s[]="Good afternoon!";

  int i,j;

  for(j=0; s[j]; j++);

  for(j--,i=0; i<j; i++,j--)

  { c=s[i];

    s[i]=s[j];

    s[j]=c;

  }

  printf("%s\n",s);

  return 0;

}

追问

这根本就不是O(1)好嘛。

追答

已有的空间不算，用于交换的辅助空间只有一个变量c，这还不叫O(1)吗？

追问

不好意思，题目给错了，应该是O(1)时间

追答

要O(1)时间，是不可能的。如果是调用系统函数的话，虽然也是一次函数调用，但时间复杂度至少也是要o(n)的。即使是求一个串长，也是需要o(n)时间的。