转一道题（csdn上的），也许它能加深你对数据结构与算法这个板块的理解。

发布于 2010-06-30 21:11， 601 次点击

问题描述：一个长度为2n的（整型）数组元素为 a1 a2 ... an b1 b2 ... bn
要求：用O(1)的空间代价, 在O(n)时间内把数组变成 a1 b1 a2 b2 a3 b3 ... an bn

这个题可以用数论知识来解。

2 回复

sxwsxw2010-07-01 22:30

简述如下：
for(i=1;i<=n-1;i+=2)
b[i]与a[i+1]交换；
for(i=2;i<=n-1;i+=2)
{a[i]与a[i+1]交换；
b[i]与b[i+1]交换；}

2010-07-02 06:28

呵呵，再想想。还有你的算法能再说清楚些吗，按我的理解，当n=3时，这个算法好像不太对.还有个小问题就是,一般a[n]与b[n]是存在同一个数组里的,即a1,a2,a3,a4.....b1,b2,b3,b4......最好能用一个数组表示。