PAT(Basic Level)1008 数组元素循环右移问题的解答和思考

PAT (Basic Level) Practice （中文）编程题1008，题目如下：
一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由（A0 A1​​ ⋯A​N−1 ）变换为（AN−M ⋯AN−1 A0 A1 ⋯AN−M−1）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
输入格式:
每个输入包含一个测试用例，第1行输入N（1≤N≤100）和M（≥0）；第2行输入N个整数，之间用空格分隔。
输出格式:
在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。
输入样例:
6 2
1 2 3 4 5 6
输出样例:
5 6 1 2 3 4

原题图片:

由于不能使用另外一个数组，我用的方法是刚开始构造的数组大小设为N+M，然后把第N-M+1到第N个元素复制到数列最后位置(即第N+1到第N+M个元素)，把第1到第N-M个元素移到第M+1到第N个元素，最后把数组末尾的第N+1到第N+M个元素移到数组最前端(即第1到第M个元素)。输出时选择第1到第N个元素即可(这里使用了序号而不是数组下标来表示，数组下标=序号-1)。

文字很难直观理解，我简单以题目给出的测试样例为例，画了示意图：
另外需要注意的一点就是，当M>N的时候，需要进行特殊处理。

C++代码如下，比较麻烦的就是各个for循环的循环变量范围了：

#include <iostream>
using namespace std;
int main(){
int n=0,num=0,temp=0;
cin >> n >>num;
while(num>n){
if(num>n){
num=num-n;
}}//这里用num%n更简单
int a[n+num]={0};
for(int i=0;i<n;i++){
cin>>temp;
a[i]=temp;
}
for(int j=0;j<num;j++){
a[n+j]=a[n+j-num];
}
for(int k=n-1;k>=num-1;k--){
a[k]=a[k-num];
}//这里要使用k--，如果从前往后会出现覆盖问题
for(int m=0;m<num;m++){
a[m]=a[n+m];
}
int count=0;
for(int p=0;p<n;p++){
count++;
cout<<a[p];
if(count!=n){
cout<<" ";
}}}

得到测试结果全部正确：

显然这不是最有效率的结果方式，判断各个循环的初始和结束位置还有循环步进方式容易出错，另外在处理num>n的情况时循环没有必要。

经过查阅其他人公开的代码，其实还有更好的方式：

1.印象最深的是使用链表，把尾部移到前部即可，节省时间和空间。参考：https://blog.csdn.net/livecoldsun/article/details/36206173

2.在输入时，直接将数放入新数组的位置。参考：https://blog.csdn.net/xlx921027/article/details/52881820