法一：
挨个遍历，每个移动K位，复杂度
[cpp]
RightShift(int* arr,int N, int K)
{
while(K--)
{
int t=arr[N-1];
for(int i=N-1;i>0;i--)
arr[i]=arr[i-1];
arr[0]=t;
}
}
RightShift(int* arr,int N, int K)
{
while(K--)
{
int t=arr[N-1];
for(int i=N-1;i>0;i--)
arr[i]=arr[i-1];
arr[0]=t;
}
}
法二：可以进一步优化，因为K远大于N时，存在重复移动，即移动存在周期性，周期就是N，所以移动K%=N就可以了
[cpp]
RightShift(int* arr,int N, int K)
{
K%=N;
while(K--)
{
int t=arr[N-1];
for(int i=N-1;i>0;i--)
arr[i]=arr[i-1];
arr[0]=t;
}
}
RightShift(int* arr,int N, int K)
{
K%=N;
while(K--)
{
int t=arr[N-1];
for(int i=N-1;i>0;i--)
arr[i]=arr[i-1];
arr[0]=t;
}
}
法三：分组逆序排序，具体过程分三步，以abcd1234移动4位为例子
逆序排列abcd：abcd1234 => dcba1234
逆序排列1234：dcba1234 =>
dcba4321
逆序排列dcba4321： dcba4321 => 1234abcd
[cpp]
Reverse(int* arr, int b, int e)
{
for(;b
{
int tmp=arr[e];
arr[e]=arr[b];
arr[b]=tmp;
}
}
RightShift(int* arr,int N, int K)
{
K%=N;
Reverse(arr,0, N-K-1);
Reverse(arr, N-K,N-1);
Reverse(arr, 0, N-1);
}
Reverse(int* arr, int b, int e)
{
for(;b
{
int tmp=arr[e];
arr[e]=arr[b];
arr[b]=tmp;
}
}
RightShift(int* arr,int N, int K)
{
K%=N;
Reverse(arr,0, N-K-1);
Reverse(arr, N-K,N-1);
Reverse(arr, 0, N-1);
}
[cpp]