arrays - 数组从 a1,..,an,b1,..,bn 移动到 a1,b1,..,an,bn

Question

今天遇到一个问题，很迷惑

问题

我有这样的数组:arr[a1, a2, a3....an, b1, b2, b3.....bn]，如何移动数组的元素将它转移到arr[a1, b1, a2, b2......an,bn]，并且你应该就地移动(空间复杂度应该是常量)。

我尽力想了想，得到了一个像冒泡排序一样丑陋的算法:

b1 moves forward by n - 1;
b2 moves forward by n - 2;
.
.
bn-1 moves forward by 1;

但是时间复杂度是O(n²)，谁能给我一个更好的算法？我找到了另一种更好的方法，就像快速排序一样:

First we swap the element from a(n/2) to a(n) with the elements from b1 to b(n/2);now we get two independent sub problems,So we can solve it by recursion.
T(n) = 2T(n/2) + O(n) 
the time complexity is O(nlgn)

这里是完整的代码:

void swapArray(int *arr, int left, int right)
{
    int mid = (left + right) >> 1;
    int temp = mid + 1;
    while(left <= mid)
    {
        swap(arr[left++], arr[temp++]);
    }
}
void arrayMove(int *arr, int lb, int le, int rb, int re)
{
    if(le - lb <= 0 || re - rb <= 0)
        return;
    int mid = (lb + le + 1) >> 1;
    int len = le - mid;
    if(rb + len >= re)
    {
        swapArray(arr, mid + 1, rb);
    }
    else
    {
        swapArray(arr, mid, rb + len);
    }
    arrayMove(arr, lb, mid - 1, mid, le);
    arrayMove(arr, rb, rb + len, rb + 1 + len, re);
}

Answer 1

在涉猎和试验/跌跌撞撞之后，我想我开始理解了，尽管数学对我来说仍然很难。我认为它是这样的:

确定转置的排列周期(这可以在实际数据传输期间或之前完成)。公式 to = 2*from mod (M*N - 1)，其中 M = 2，N = 数组长度/2，可用于查找索引目标(排列)。 (因为我们知道 M = 2，所以我减少了这个问题的公式。)访问索引的标记可以帮助确定下一个循环的开始(从技术上讲，可以使用循环计算而不是位集作为标记，只保留内存中的下一个循环开始)。临时变量保存从起始地址到循环结束的数据。

总而言之，这可能意味着两个临时变量、循环计算和每个数组元素一次就地移动。

例如:

arr          = 0,1,2,3,4,5,6,7,8,9
destinations:  0,2,4,6,8,1,3,5,7,9

start = 1, tmp = arr[1]    

cycle start
5->1, 7->5, 8->7, 4->8, 2->4, tmp->2
cycle end

not visited - 3

start = 3, tmp = arr[3]

cycle start
6->3, tmp->6
cycle end

Transposition complete.

有什么问题吗？
随时询问，请访问http://en.wikipedia.org/wiki/In-place_matrix_transposition