Question

请编写函数实现一个整数数组的循环右移,要求时间复杂度不能超过O(n)

空间复杂度尽量小，如1，2，3，4，5则循环右移两个元素后结果4，5，1，2，3
右移和左移的详细代码或思路

楼下那位怎么每次只是右移一位呢还有
//以 6 2为例,具体过程为
// 3 2 1 4 5 6
//5 2 1 4 3 6
//5 4 1 2 3 6
//5 6 1 2 3 4、、这是循环右移2位结果吗

Answer 1

//楼主加点分吧，昨晚从12点半写到2点O(∩_∩)O....
#include <stdio.h>
#define N 60
int naddr=0,faddr=0,m,f=0;//naddr:当前要交换数据的游标号，faddr:即将移动到的游标号
#define swap(x,y,z){z=x,x=y,y=z;}//注意这里不是函数，是宏定义
void calculate()
{
faddr=(faddr+m)%N;
if(naddr==faddr)//自身交换
f=1;
}
void Init()
{
faddr=naddr=(naddr+1)%N;
calculate();
}
int main()
{
int k=0,a[N],t; //K 记录交换次数，宏观上要交换N-1次
for(t=0;t<N;t++)
a[t]=t+1;
scanf("%d",&m);
while(k<N-1)
{
calculate();
if(f)//出现自身与自身交换
{
Init();//赋新值
f=0;
k++;//注意这里，出现自身与自身交换的时候说明前面的交换过程正好完成一次循环，比如N=6时会出现5，2，1，4，3，6，
//这时 f(6)=f(3)+f(3)=2+2=4,即N=6时只要交换4次就足够了，同理可推广至其它情况：每出现一次循环就可以少交换一次。
}
swap(a[naddr],a[faddr],t)//交换数据
k++;
}
for(t=0;t<N;t++)
printf("%d ",a[t]);
printf("\n");
return 0;
}
//t和f其实只要一个就够了，如果确实需要节省这一个变量的空间，可以自己修改下
//采用交换的方法，时间和空间复杂度都是O(n);
//以 6 2为例,具体过程为
// 3 2 1 4 5 6
//5 2 1 4 3 6
//5 4 1 2 3 6
//5 6 1 2 3 4 这不是循环右移的结果？？？
怎么每次只是右移一位呢——不是右移一位啊，是每次把一个数据移动到正确位置，K每加1就有一个元素到达正确位置

Answer 2

//楼主加点分吧，昨晚从12点半写到2点O(∩_∩)O....
#include
#define
N
60
int
naddr=0,faddr=0,m,f=0;//naddr:当前要交换数据的游标号，faddr:即将移动到的游标号
#define
swap(x,y,z){z=x,x=y,y=z;}//注意这里不是函数，是宏定义
void
calculate()
{
faddr=(faddr+m)%N;
if(naddr==faddr)//自身交换
f=1;
}
void
Init()
{
faddr=naddr=(naddr+1)%N;
calculate();
}
int
main()
{
int
k=0,a[N],t;
//K
记录交换次数，宏观上要交换N-1次
for(t=0;t
评论
0
0
加载更多

Answer 3

搜一下：请编写函数实现一个整数数组的循环右移,要求时间复杂度不能超过O(n)