试设计一个算法,将数组A(0..n-1)中的元素循环右移k位,并要求空间复杂度为O(1),时间复杂度为O(n)。

时间:2021-05-06 04:26:42
以1 2 3 4 5 6 7 8 9 10,向右移动2位为例 :  1、将1 2 3 4 5 6 7 8 反转 1 2 3 4 5 6 7 8 9 10 => 8 7 6 5 4 3 2 1 9 10 2、将9 10反转 8 7 6 5 4 3 2 1 9 10=>  8 7 6 5 4 3 2 1 10 9 3、将整个串反转 8 7 6 5 4 3 2 1 10 9=>9 10 1 2 3 4 5 6 7 8
实现了右移2位的操作。 Code(C):
#include<stdio.h>

void tran(int a[],int k,int n);
void reverse(int a[],int s,int e);

int main()
{
int a[10] = {1,2,3,4,5,6,7,8,9,10};
int k,i;
printf("请输入右移的次数\n");
scanf("%d",&k);
tran(a,k,10);
for(i = 0;i < 10;i++)
{
printf("%d ",a[i]);
}
printf("\n");
return 0;
}

void tran(int a[],int k,int n)
{

if(k >= n)
k = k%n;
reverse(a,0,n-k-1);
reverse(a+(n-k),0,k-1);
reverse(a,0,n-1);
}

void reverse(int a[],int s,int e)
{
int temp;
while(s < e)
{
temp = a[s];
a[s] = a[e];
a[e] = temp;
s++;
e--;
}

}