Chinaunix首页 | 论坛 | 博客
  • 博客访问: 768274
  • 博文数量: 199
  • 博客积分: 3584
  • 博客等级: 中校
  • 技术积分: 2193
  • 用 户 组: 普通用户
  • 注册时间: 2008-05-12 21:18
文章分类

全部博文(199)

文章存档

2018年(6)

2013年(14)

2012年(30)

2011年(28)

2010年(24)

2009年(86)

2008年(11)

分类: C/C++

2009-06-14 22:12:07

面试题
 
[ 2005-12-2 14:36:00 | By: 俊豪 ]
 
  //华为面试题:  有1,2,....一直到n的无序数组,求排序算法,
//并且要求时间复杂度为O(n),空间复杂度O(1),使用交换,而且一次只能交换两个数.
//评论:要使时间复杂度为O(n),那一定是特殊数组,否则不可能实现,
//题目给出数组为1,2,....n,那么可以在这上面做文章,把数组的值和数组的下标联系起来,把a[i]的值给
a[a[i]-1],比如a[3]=5,则把5赋给a[5-1]也就是a[4]=5,则符合要求了。
#i nclude
void main()
{ int a[10]={3,6,8,4,2,9,7,1,5,10};//{6,3,4,8,2,9,7,1,5,10}; 这个数例不行
  int b,i;
  for(i=0;i<10;i++)
  {
   b=a[a[i]-1];
    a[a[i]-1]=a[i];
    a[i]=b;
  }
  for(i=0;i<10;i++)
   printf("%d ",a[i]);
}
#i nclude
#i nclude
int print( int*, int );
int swap( int&, int& );
int main()
{
int *a, n, i;
scanf( "%d", &n );
a = ( int* ) malloc ( ( n + 1 ) * sizeof( int ) );
for( i = 1; i <= n; i++ )
a[i] = i;
for( i = 1; i <= n; i++ )
swap( a[i], a[rand()%n+1] );
print( a, n );
for( i = 1; i <= n; i++ )
{
while( a[i] != i )
swap( a[i], a[a[i]] );
}
print( a, n );
return 0;
}
int swap( int &i, int &j )
{
int temp = i;
i = j;
j = temp;
return 0;
}
int print( int a[], int n )
{
int i;
for( i = 1; i <= n; i++ )
printf( "%4d", a[i] );
printf( "\n" );
return 0;
}
//惠通面试题:两个字符串,s,t;把t字符串插入到s字符串中,s字符串有足够的空间存放t字符串
void insert(char *s, char *t, int i);
void insert(char *s, char *t, int i)
{
char *q = t;
char *p = s;
if(q == NULL)return;//子串为空
while(*p!='\0')
{
p++;
}  //移到目标串串尾
while( (*p = *q) != '\0')
{
    p++;
    q++;
}
/*
while(*q!='\0')
{
*p = *q;
p++;
q++;
}//插入
*p = '\0';
*/
}
 
 
阅读(662) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~