PAT Basic Level 1008 *

1008. 数组元素循环右移问题 (20)

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

一个数组A中存有N（N>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（M>=0）个位置，即将A中的数据由（A₀ A₁……A_N-1）变换为（A_N-M …… A_N-1 A₀ A₁……A_N-M-1）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入格式：每个输入包含一个测试用例，第1行输入N ( 1<=N<=100)、M（M>=0）；第2行输入N个整数，之间用空格分隔。

输出格式：在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

输入样例：

6 2
1 2 3 4 5 6

输出样例：

5 6 1 2 3 4


思路：由于题目直接输出移动好的数组，所以不用考虑在数组上进行修改的问题，直接输出即可。
右移 m 位，即将最后 m % n 个元素先输出，最后依序输出前面的数据。
例

AC 代码

 1 #include <stdio.h>
 2 int main ()
 3 {
 4     int array[100] = {0};
 5     int ret[100] = {0};
 6     int step;
 7     int size;
 8     scanf("%d %d",&size,&step);
 9     int flag = 0;
10     for (flag = 0;flag < size;flag++)
11     {
12         scanf("%d",&array[flag]);
13     }
14     int i;
15     for(flag = 0;flag < size;flag++)
16     {
17         i = (flag+step)%size;
18         ret[i] = array[flag];
19     }
20     for(i = 0;i < size;i++)
21     {
22         printf("%d",ret[i]);
23         if(i != size - 1)
24         {
25             printf(" ");
26         }
27     }
28     return 0 ;
29  }

反思：如果给定一个数组让该数组左移呢？

法一：再开一个数组

容易想到再开一个数组，依次读取该数组每一位将其写入重开数组相应位置。

但其时间复杂度O(n),空间复杂度O（n），空间复杂度太大。

法二：数组逆序

法三：原数组上移动

例：数组1,2,3,4,5，6。右移2位。 1移到3,3移到5,5移到1。显然还有数字没有动过。所以2移到4,4移到6,6移到2，

总共2组，呢么如何知道一共有多少组呢？只需求2,6的最大公约数。

即每个元素m移到(m+k) % n的位置上，而(m+k)%n移到(m+2k)%n的位置上……

当n与k互质时，可以证明m, m+k, m+2k, ..., m + (n-1)k模n的结果互不相等，刚好构成一个循环（如5个元素右移3位）；否则，会构成(n,k)（n与k的最大公约数）个循环。分别处理这(n,k)个循环就可以得到结果。

难以理解为什么正好是最大公约数个循环。标记之，解决后附上相应代码。