多谢五楼的回答。。这样用三个逆置简单明了。。我用下面的方法，但觉得有点别扭，呵。。
#include
#include
#defineMAX100
boolcheck[MAX];//checkwhethertheentryhasbeenrotatedintherightplace
intarray[MAX];//storagetheentry
intn;//thenumberofthearray
intk;//thesteps
voidrotate(){
inti=k;
inttemp,tt;
memset(check,false,sizeof(check));
for(intj=0;j
#include
#include
#include
size_tgcd(size_tm,size_tn)
{
returnn==0?m:gcd(n,m%n);
}
voidrotate(int*arr,size_tn,intk)//n:数组长度，k:右移位数
{
size_td=gcd(n,(k>0?k:-k));//获得n和|k|的最大公约数
for(size_ti=0;i
对于可随机访问的数组,有比三次convert更快的算法,如上所示(STL中对RandomAccessIterator即使用此算法).
LZ的算法与此相同,只不过不需要check.数学上可以证明只要循环gcd(n,k)次就可遍历所有元素恰好一次.
该算法的时间复杂度为n+gcd(n,k),即每个数组元素恰好赋值一次,每个循环需有一次临时变量的赋值.
|
