假设有一个数组,我们想要找到奇数索引中的所有内容(索引从0开始),并将其移动到最后.偶数索引中的所有内容都将其移至开头.保留所有奇数索引项和所有偶数索引项的相对顺序.
即如果阵列是
a1 b1 a2 b2 ... an bn
手术后就变成了
a1 a2 a3 ... an b1 b2 ... bn
这可以在O(n)时间内就地完成吗？
小智 7
这是可能的,但它非常复杂!更简单的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)时间).
现在我们可以看到排列的循环(参见上面的文章/ stackoverflow链接)
2 ^一个*3 ^ B
其中0 <= a <k,0 <= b <m.
所以你从每个可能的对(a,b)开始,并按照排列的循环,这给出了O(n)时间,就地算法,因为你触摸每个元素不超过一定的次数!
这有点简短(!)如果您需要更多信息,请告诉我.