相关疑难解决方法(0)

如果我有一个N大小的对象数组,并且我有1 ... N范围内的唯一数字数组,是否有任何算法按照数字列表指定的顺序就地重新排列对象数组,并且但是在O(N)时间呢？

上下文:我正在对大小相当大的对象进行快速排序算法,因此在索引上进行交换比在对象本身上进行交换更快,并且只在最后一次传递中移动对象.我只是想知道我是否可以做最后一次传递而不为单独的数组分配内存.

编辑:我不是问如何在O(N)时间内进行排序,而是如何在O(1)空间的O(N)时间内进行后排序重排.很抱歉没有说清楚.

我发现了关于将两个arraylists交织成一个的类似问题,但它在PHP中.我在面试中也被问到这个问题,但无法解决,回到SO看看是否已经解决,但我只能找到这篇 论文

那么任何指向伪代码或方法定义的指针呢？

大(O)限制:O(n) - 时间成本和O(1) - 空间成本

示例:
a [] = a1,a2,...,
a b [] = b1,b2,...,bn
将arraylist重新排列为a1,b1,a2,b2,...,an,bn

Editv1.0:Arraylists a []和b []具有相同的大小

Editv2.0:如果问题扩展到在给定的两个数组中重新排列,但是没有创建新数组怎么办？

我必须交错给定的表单数组

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

作为

{a1,b1,a2,b2,a3,b3} 

在 O(n) 时间和 O(1) 空间中。

例子：

Input - {1,2,3,4,5,6}
Output- {1,4,2,5,3,6}

这是按索引排列的元素：

Initial Index    Final Index
 0                   0
 1                   2
 2                   4
 3                   1
 4                   3
 5                   5

通过一些例子的观察，我发现ai (i<n/2) goes from index (i) to index (2i)& bi (i>=n/2) goes from index (i) to index (((i-n/2)*2)+1). 您可以自行验证。如果我错了，请纠正我。

但是，我无法在代码中正确应用此逻辑。

我的伪代码：

for (i = 0 ; i < n ; i++)
    if(i < n/2)
        swap(arr[i],arr[2*i]);
    else
        swap(arr[i],arr[((i-n/2)*2)+1]);

它不起作用。

如何编写算法来解决这个问题？