王道 数据结构 p17 第10题
基本设计思路：将数组R分为a、b两个小数组，a数组是前p个元素，b数组是a在R中的补集；分别将a、b两个数组逆置，再对经上一步逆置之后的R数组整体逆置，用到矩阵中（a-1b-1）-1=ba的思想。
#include<iostream>
using namespace std;
void reverse(int R[],int left,int right)
{
for(int i=left;i<=(left+right)/2;i++)
{
int temp=R[right+left-i];
R[right+left-i]=R[i];
R[i]=temp;
}
}
void moveR(int R[],int n,int p)
{
reverse(R,0,p-1);//时间按复杂度 O(p/2)
reverse(R,p,n-1);//时间按复杂度 O((n-p)/2)
reverse(R,0,n-1); //时间按复杂度 O(n/2)
}
/*法二：这种方法比较容易想到，先找一个S数组用来盛放前p个元素，即第一种方法中的a数组，然后把剩下的元素前移p位，最后把S再拼接到原数组末尾。
void moveR2(int R[],int n,int p)
{
int S[p],k=0,i;
for(i=0;i<p;i++)
{
S[k++]=R[i];
}
for(;i<n;i++)
{
R[i-p]=R[i];
}
int j=i-p;
for(k=0;k<p;k++)
{
R[j++]=S[k];
}
}此方法时间复杂度O(n),空间复杂度O(p)
*/
int main(){
int n=0,p=0;
cout<<"请输入n:";
cin>>n;
int R[n];
for(int i=0;i<n;i++)
{
cout<<"请输入第"<<i+1<<"个数字:";
cin>>R[i];
}
cout<<"请输入p:";
cin>>p;
moveR(R,n,p);
for(int i=0;i<n;i++)
{
cout<<R[i]<<" ";
}
}
时间复杂度是O(n),空间复杂度是O(1)
