Question

今天参加了华为的面试，被一个算法题水了？如下：

一个C语言数组：围成一圈，现在给你一个步长, 要求每个元素按照步长移位，最后输出数组
比如a[]={1,2,3,4,5,6,7};步长2
要把1放在3那个位置，3放在5那个位置，5放在7那个位置，7放在2那个位置，2放在4那个位置...
时间复杂度为O（n）,空间复杂度越小越好

Answer 1

根据要求修改了,复杂度为O(n),没有引入额外的数组:)
#include <stdio.h>
#define N 7
void main(){
int a[N],step,temp;
printf("输入%d个整数:\n",N);
for(int l=0;l<N;l++)
scanf("%d",&a[l]);
printf("输入步长:\n");
scanf("%d",&step);
step=step%N;
int k=0,n=0;
for(int i=step;i<N+step;i++,k++){
if(step)
k=k%step;
n=i%N;
temp=a[n];
a[n]=a[k];
a[k]=temp;
}
printf("输出移位后的数组:\n");
for(int m=0;m<N;m++)
printf("a[%d]=%d\n",m,a[m]);
}

Answer 2

应该有判错机制 并不是所有的组合 数组的各位都可以得到移动
举例
1-8 步长为2 移动的永远是
1 3 5 7
然后利用加步长与数组长度求余得到移动地址 然后保存赋值即可

设立标志数组，实现判定结束和在不满足情况下返回

Answer 3

运行通过。代码如下：
#include <iostream>
using namespace std ;
int * re_pai( int a[], int n )
{
int i ;
int *b ;
b = new int[ n ] ;
for( i = 0 ; i < n ; i++ )
{
b[ (i +2) % n ] = a[ i ] ;
}
return b ;
}
int main()
{
int a[]={1,2,3,4,5,6,7};
int *b = re_pai( a, 7 ) ;
int i ;
for( i = 0 ; i < 7 ; i++)
{
cout << b[ i ] <<" " ;
}
delete b ;
return 0 ;
}

Answer 4

好难