P*******b
发帖数: 1001 | 1 Thanks！
An array which contains 2 N elements needs to be arranged from
a1, a2, a3, ..., an, b1, b2, b3, ..., bn
to
a1, b1, a2, b2, a3, b3, ..., an, bn. | d**e
发帖数: 6098 | 2 印象中好像在careercup见过，但一时间却又找不到。
大概的方法好像是
1. 分成四部分 a1 ~ a_{n/2}, a_{n/2 + 1} ~ an, b1 ~ b_{n/2}, b_{n/2 + 1} ~ bn
a) b) c) d)
2. 交换b)和c)两部分
3. 递归处理 {a), c)} 和{b), d)} 两部分
【在 P*******b 的大作中提到】
: Thanks！
: An array which contains 2 N elements needs to be arranged from
: a1, a2, a3, ..., an, b1, b2, b3, ..., bn
: to
: a1, b1, a2, b2, a3, b3, ..., an, bn.
| P*******b
发帖数: 1001 | 3 这个应该有问题，n不是2的幂的时候搞不定
bn
【在 d**e 的大作中提到】
: 印象中好像在careercup见过，但一时间却又找不到。
: 大概的方法好像是
: 1. 分成四部分 a1 ~ a_{n/2}, a_{n/2 + 1} ~ an, b1 ~ b_{n/2}, b_{n/2 + 1} ~ bn
: a) b) c) d)
: 2. 交换b)和c)两部分
: 3. 递归处理 {a), c)} 和{b), d)} 两部分
| d**e
发帖数: 6098 | 4 嗯，没错，我才意识到这个问题。
要再想想。
【在 P*******b 的大作中提到】
: 这个应该有问题，n不是2的幂的时候搞不定
:
: bn
| d**e
发帖数: 6098 | 5 O(n)时间, O(n)空间的简单，不用说了。
如果O(1)空间的，我只能想到O(n^2)时间.
把它分上下两行看比较清楚。
b1, b2, b3, ...., bn
a1, a2, a3, ...., an
方法就是斜线交换
swap(a2, b1), swap(a3, b2)... swap(an, b_{n-1})
这样就处理好b1和an
a2, a3, .... an, bn
a1, b1, b2...... b_{n-1}
然后再隔一个交换，swap(b2, a2), swap(b3, a3) ...
处理好了a2和b_{n-1}
再斜线隔两个交换，如此类推.... | P*******b
发帖数: 1001 | 6 thanks版主大人
【在 d**e 的大作中提到】
: O(n)时间, O(n)空间的简单，不用说了。
: 如果O(1)空间的，我只能想到O(n^2)时间.
: 把它分上下两行看比较清楚。
: b1, b2, b3, ...., bn
: a1, a2, a3, ...., an
: 方法就是斜线交换
: swap(a2, b1), swap(a3, b2)... swap(an, b_{n-1})
: 这样就处理好b1和an
: a2, a3, .... an, bn
: a1, b1, b2...... b_{n-1}
|
|
