题目描述:将长度为N的数组arr循环右移K位,给出最高效的算法
//最高效的循环右移算法!!
//这个是递归的写法
//author:tengzhao201 QQ:715572192
//time:2010-4-24
//时间复杂度为O(n),空间复杂度O(1),交换点在中间时比逆序法快一倍!!!
//提速要点:由于取模运算的效率很低,去掉了取模运算后效率得到大提升;swap函数效率低,引入了temp变量
void TZshift1(int* arr,int N,int K)
{
K=K%N;
if(0==K)return;
int temp,qq,pp=0;
pp=0;qq=K;
for(int i=0;i<N-K;i++,pp++,qq++)
{
//swap(arr[i%K],arr[i+K]);//问题的关键在于找到原来的第i个元素现在在哪里,通过观察可以发现在a[i%K]的位置,下面的代码实现了a[i%K]和a[i+K]的互换
if(K==pp)pp=0;
temp=arr[pp];
arr[pp]=arr[qq];
arr[qq]=temp;
}
TZshift1(arr,K,K-pp);
}