华为慧通面试题.docx

华为慧通面试题〃华为面试题： 有1,2, ••一直到n的无序数组，求排序算法，〃并且要求时间复杂度为 O(n),空间复杂度 0(1)，使用交换，而且一次只能交换两个数.〃评论：要使时间复杂度为 0(n),那一定是特殊数组，否则不可能实现，〃题目给由数组为1,2,….啷么可以在这上面做文章， 把数组 的值和数组的下标联系起来，把 a[i]的值给a[a[i]-1],比如 a[3]=5,则把5赋给a[5-1]也就是a[4]=5 ,则符合要求了 i ncludevoid main(){ int a[10]={3,6,8,4,2,9,7,1,5,10};〃{6,3,4,8,2,9,7,1,5,10}; 这个数例不行for(i=0;i# i ncludeint 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 );)int swap( int &i, int &j )(int temp = i;i = j；j = temp;return 0;)int print( int a[], int n )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(*q!= ' 0')*p = *q;p++；q++；}//插入*p = ，0。