Question

设计一个时间复杂度为O（n）的算法，是先将数组A【n】中所有元素循环右移k个位置

Answer 1

你先全部复制出来不就可以很方便了嘛，并且还是满足O（n）的。

当然如果所有数据想原地操作也是可以的，不过相当麻烦。先要算n和k的最大公约数m。把a[]分成m组（不需要真的分开），然后每组各自循环移动。
举个例子，假设n=8,k=6
数组下标：0,1,2,3,...，7
这样就分成两组，分别移动：
7 <- 1 <- 3 <- 5 <- 7(原来的)
6 <- 0 <- 2 <- 4 <- 6(原来的)
每组移动时只要多用一个临时空间就可以了。
但个人认为没必要这么搞，太复杂了，就用第一种方法，简单方便，而且符合要求。

#include <iostream>
using namespace std;

void RightMove(int *a,int n,int k){
int i,*temp;
k%=n;
if(k==0)
return;
temp=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
temp[i]=a[i];
for(i=0;i<k;i++)
a[i]=temp[i+n-k];
for(;i<n;i++)
a[i]=temp[i-k];
free(temp);
}
int main(){
int i;
int a[10]={1,2,3,4,5,6,7,8,9,0};
RightMove(a,10,3);
for(i=0;i<10;i++)
printf("%d ",a[i]);

return 0;
}