可以，但是非常复杂！在缓存方面，更简单的O（nlogn）和O（1）空间解决方案可能更好。

我们将解决与您的问题不同的问题，但是一旦我们解决了问题，您的问题将变得微不足道。

考虑数组为

b1, a1, b2, a2, ..., bn, an

你必须将其转换为

a1, a2, ..., an, b1, b2, ..., bn

使用索引1到2n，

我们看到这是由

i -> (n+1)*i (mod 2n+1).

O（nlogn）时间O（1）空间解

我们可以如下使用分而治之。

首先对于接近n / 2的m进行转换

b1, a1, ..., bn , an

至

a1,a2,...am, b1,b2, ..bm, a(m+1), ..., an, b(m+1), ... , bn

递归地应用到前2m个元素，然后再应用其余元素。

现在我们要做的是使中间数组循环移位m个点（这可以在O（n）时间和O（1）空间中完成）

给

a1, a2, .., am , a(m+1), ..., an, b1, b2, ..., bm, b(m+1), ..., bn.

当然，正如IVlad指出的那样，这需要O（logn）堆栈空间。我们可以通过以下操作解决此问题：

我们有：

b1 a1, b2 a2, .. bm am, b(m+1) a(m+1), ..., bn an

现在在阵列的后半部分交换对以得出

b1 a1, b2 a2, .. bm am, a(m+1) b(m+1), ..., an bn

现在将元素循环移位到奇数位置： b1, b2, .., bm, a(m+1), a(m+2) ..., a(n).

这给像

a(m+1) a1, a(m+2) a2, ..., a(2m) am, a(2m+1) b(m+1),...,an b(n-m), b1 b(n-m+1),...,bm bn

现在再次交换数组的后半部分

a(m+1) a1, a(m+2) a2, ..., a(2m) am, b(m+1) a(2m+1),...,b(n-m) an,b(n-m+1) b1,..., bn bm

现在递归求解第一部分和第二部分给出

[a1 a2 ... am][a(m+1) ... a(2m)]   [a(2m+1) ...an b1 b2 .. bm][b(m+1) ... bn]

无论2m> = n，该方法均有效。

因此，这是O（nlogn）时间和O（1）空间算法。

O（n）时间O（1）空间解。

使用的想法与以下论文中使用的想法类似： 一种用于Inshuffle的简单就地算法。

您需要阅读该文件才能理解以下内容。

这基本上是上述论文中解决的逆排列。

当2n + 1是3 =（3 ^ m说）的幂时，足以解决此问题，因为在此之后我们可以使用分治法（例如O（nlogn）解决方案）。

现在2n + 1和n + 1是相对质数，因此对3 ^ m进行模运算，我们看到n + 1 必须 是2的幂。（再次参见该论文以了解原因：基本上任何以3 ^
m为模的数都是3 ^ m的相对素数是2的幂，再次取模3 ^ m。

假设n + 1 = 2 ^ k（我们尚不知道k，请注意，这是模3 ^ m）。

找出k的一种方法，计算n + 1模3 ^ m的幂，直到变为1。这将给我们k（最多为O（n）时间）。

现在我们可以看到置换的周期（请参见上面的paper / stackoverflow链接）从

2 ^ a * 3 ^ b

其中0 <= a <k，0 <= b <m

因此，您从每个可能的对（a，b）开始并遵循置换的周期，当您触摸每个元素的次数不超过恒定次数时，这将提供O（n）时间的就地算法！

这有点简短（！），如果您需要更多信息，请告诉我。