当前位置: 首页 > >

数组交换

发布时间:



设a[0:n-1]是有n个元素的数组, k(0<=k<=n-1) 是一个非负整数。试设计一个算法将子数组a[0:k-1]? 与 a[k:n-1]?换位。要去算法在最坏情况下耗时?O(n),且只用到O(1)的辅助空间。

#include
using namespace std;
const int maxn = 10000;
void rev1(int a[], int l, int r)//逆置数组;
{
int t;
for(int i = l; i<=(l+r)/2; i++)
{
t = a[i];
a[i] = a[r - (i - l)];
a[r - (i - l)] = t;
}
}
void change(int a[], int n, int p)//交换;
{
int t ;
for(int i = 1; i<=p; i++)
{
t = a[i];
a[i] = a[n - p + i];
a[n - p + i] = t;
}
}int main()
{
int n;
cin>>n;//数组的大小;
int a[10000];
for(int i = 1; i<= n; i++)
{
a[i] = i - 1;
}
int k;
cin>>k;//要交换的长度;
/*逆置的部分也可以直接调用reverse()函数*/ rev1(a,k+1,n); //将a[k+1]到a[n]逆置,
change(a,n,k);//将a[1]到a[k]与当前的a[n-k+1]到a[n]交换;
rev1(a,k+1, n-k);//将a[1]到a[k]逆置;
rev1(a, 1, k);//将a[k+1]到a[n-k]逆置,
for(int i = 1; i<=n; i++)
{
printf("%d ",a[i]);
}
return 0;
}














友情链接: