从A1阵列移动，......，一个，B1，...，bn的对A1，B1，..，一个，BN [英] Array movement from a1,..,an,b1,..,bn to a1,b1,..,an,bn

问题描述

今天，我遇到了一个问题，这是真的困惑了我

问题

我有阵只是想：改编[A1，A2，A3 ....一个，B1，B2，B3 ..... BN] ，如何移动数组中的元素将其转移到改编[A1，B1，A2，B2 ......一，BN] ，你应该做的运动-place（空间复杂度应该是恒定）。

我尽力了思考，并得到一个丑陋的算法就像冒泡排序：

  B1向前移动N  -  1;
B2向前移动N  -  2;
。
。
BN-1向前移动1;
 

但时间复杂度为O（n ² ），谁可以给我一个更好的算法？ 我找到另外一个更好的方法，就像快速排序：

 首先，我们交换元件从（N / 2）到（N）的元素，从B1至B（N / 2）;现在我们得到两个独立的子问题，因此，我们可以通过递归解决它。
T（N）= 2T（N / 2）+ O（N）
时间复杂度为O（nlgn）
 

下面是完整的codeS：

 无效swapArray（INT *改编，诠释左，右诠释）
{
    INT中期=（左+右）＆GT;＆GT; 1;
    INT TEMP =中端+ 1;
    而（左＆LT; = MID）
    {
        掉期（ARR [左++]，编曲[临时++]）;
    }
}
无效arrayMove（INT *改编，诠释磅，诠释乐，INT RB，INT重）
{
    如果（LE  - 磅＆LT; = 0 ||重 -  RB＆LT; = 0）
        返回;
    INT中期=（LB +了+ 1）＆GT;＆GT; 1;
    INT LEN =乐 - 中;
    如果（RB + LEN＆GT; =重）
    {
        swapArray（ARR，中+ 1，RB）;
    }
    其他
    {
        swapArray（ARR，中，RB + LEN）;
    }
    arrayMove（ARR，磅，中期 -  1，中，下）;
    arrayMove（ARR，RB，RB + len个，RB + 1 + len个，重）;
}
 

解决方案

涉猎和试验/绊倒了一点后，我觉得我开始明白，虽然数学依然对我来说很难。我认为它是这样的：

确定换位的排列周期（这可以在或实际的数据传输之前进行）。式中，来= 2 *从MOD（M * N - 1），其中M = 2，N =数组长度/ 2 ，可用于查找指数目的地（排列）。 （Ⅰ减少式为这个问题，因为我们知道，M = 2）的标志访问了索引可以帮助确定下一个周期的开始（从技术上来说，人们可以使用周期计算，而不是一个位集合作为标记，只保留下一周期启动在内存中）。临时变量保存从起始地址的数据，直到周期结束。

总之，这可能意味着两个临时变量的周期计算，并且在就地每个数组元素的一招。

例如：

  ARR = 0,1,2,3,4,5,6,7,8,9
目的地：0,2,4,6,8,1,3,5,7,9

开始= 1，TMP = ARR [1]

周期开始
5→1，7-大于5，8-大于7，4-→8，2-→4，tmp-→2
周期结束

没有访问 -  3

开始= 3，TMP =改编[3]

周期开始
6-→3，tmp-→6
周期结束

换位完成。
 

有问题吗？
随意问及，请访问 http://en.wikipedia.org/wiki/In-place_matrix_transposition

Today, I met a question which is really puzzled me

Question

I have array just like:arr[a1, a2, a3....an, b1, b2, b3.....bn], how to move the elements of the array to transfer it into arr[a1, b1, a2, b2......an,bn], And you should do the movement in-place（space complexity should be constant）.

I tried my best to think it over and get an ugly algorithm just like bubble-sort:

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

But the time complexity is O(n²), who can give me a better algorithm? I find another better method just like quick-Sort:

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)

here are whole codes:

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);
}

解决方案

After dabbling and experimenting/stumbling a little, I think I'm beginning to understand, although the math is still hard for me. I think it goes something like this:

Determine the permutation cycles of the transposition (this can be done during or before the actual data transfer). The formula, to = 2*from mod (M*N - 1), where M = 2, N = array length / 2, can be used to find the index destinations (permutation). (I reduced the formula for this question since we know M = 2.) A marker of visited indexes can help determine the start of the next cycle (technically speaking, one could use the cycle calculations rather than a bitset as a marker, keeping only the next cycle-start in memory). A temporary variable holds the data from the start address until the cycle-end.

Altogether, that could mean two temporary variables, the cycle calculations, and one move in-place per array element.

For example:

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.

Any questions?
Feel free to ask and please visit http://en.wikipedia.org/wiki/In-place_matrix_transposition

这篇关于从A1阵列移动，......，一个，B1，...，bn的对A1，B1，..，一个，BN的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！