arrays - 在恒定空间中交错数组

Question

假设我们有一个数组 a1, a2,... , an, b1, b2, ..., bn。

目标是在 O(n) 时间和 O(1) 空间内将此数组更改为 a1, b1, a2, b2, ..., an, bn。换句话说，我们需要一个线性时间算法来就地修改数组，而额外的存储量不超过恒定量。

如何才能做到这一点？

Answer 1

这是我用笔和纸制定的顺序和笔记。我认为它或一个变体将适用于任何更大的 n。

每行代表一个不同的步骤，() 表示此步骤移动的内容，[] 表示从上一步移动的内容。数组本身用作存储，需要两个指针（一个用于 L，一个用于 N）来确定下一步要移动什么。L 表示“字母线”，N 表示“数字线”（移动的内容）。

   ABCD 1 2 3 4

LABC (D) 1 2 3 4 首先是L，不需要最后移动N
NABC (3) 1 2 [D] 4
实验室 (C) 2 1 [3] D 4
NAB 1 (2) [C] 3 D 4
洛杉矶 (B) 1 [2] C 3 D 4
北美 (1) [B] 2 C 3 D 4
   A [1] B 2 C 3 D 4 完成，无需移动 A

注意不同的“指针跳转”——L 指针总是递减 1（因为它不能比这更快地被吃掉），但是 N 指针根据它是否“替换自己”而跳转（在现场，跳下两个）或如果它交换了一些东西（没有跳跃，所以下一个东西可以开始了！）。

Answer 2

这个问题并不像看起来那么容易，但经过一番思考，完成这个问题的算法还不错。你会注意到第一个和最后一个元素已经就位，所以我们不需要担心它们。我们将保留一个左索引变量，它表示数组前半部分中需要更改的第一项。之后，我们将一个右索引变量设置为需要更改的数组第二半部分中的第一项。现在我们所做的就是将右侧索引处的项目一个接一个地向下交换，直到它到达左侧索引项。将左侧索引增加 2，将右侧索引增加 1，并重复直到索引重叠或左侧超过右侧索引（右侧索引将始终在数组的最后一个索引处结束）。

伪代码

1. 将左索引设置为 1
2. 将右索引设置为中间（数组长度/2）
3. 将右侧索引处的项目与它之前的项目交换，直到它替换左侧索引处的项目
4. 将左索引增加 2
5. 将右索引增加 1
6. 重复 3 到 5，直到左侧索引大于或等于右侧索引

C(#)中的交织算法

protected void Interleave(int[] arr)  
{  
    int left = 1;  
    int right = arr.Length / 2;  
    int temp;  

    while (left < right)  
    {  
        for (int i = right; i > left; i--)  
        {  
            temp = arr[i];  
            arr[i] = arr[i - 1];  
            arr[i - 1] = temp;  
        }  

        left += 2;  
        right += 1;  
    }  
}    

该算法使用 O(1) 存储（使用临时变量，可以使用加法/减法交换技术消除）我不太擅长运行时分析，但我相信这仍然是 O(n)，即使我们'重新执行许多交换。也许有人可以进一步探索它的运行时分析。

Answer 3

It's called in-place in-shuffle problem. Here is its implementation in C++ based on here.

void in_place_in_shuffle(int arr[], int length)
{
    assert(arr && length>0 && !(length&1));

    // shuffle to {5, 0, 6, 1, 7, 2, 8, 3, 9, 4}
    int i,startPos=0;
    while(startPos<length)
    {
        i=_LookUp(length-startPos);
        _ShiftN(&arr[startPos+(i-1)/2],(length-startPos)/2,(i-1)/2);
        _PerfectShuffle(&arr[startPos],i-1);
        startPos+=(i-1);
    }

    // local swap to {0, 5, 1, 6, 2, 7, 3, 8, 4, 9}
    for (int i=0; i<length; i+=2)
        swap(arr[i], arr[i+1]);
}

// cycle
void _Cycle(int Data[],int Lenth,int Start)
{
    int Cur_index,Temp1,Temp2;

    Cur_index=(Start*2)%(Lenth+1);
    Temp1=Data[Cur_index-1];
    Data[Cur_index-1]=Data[Start-1];

    while(Cur_index!=Start)
    {
        Temp2=Data[(Cur_index*2)%(Lenth+1)-1];
        Data[(Cur_index*2)%(Lenth+1)-1]=Temp1;
        Temp1=Temp2;
        Cur_index=(Cur_index*2)%(Lenth+1);
    }
}


// loop-move array
void _Reverse(int Data[],int Len)
{
    int i,Temp;
    for(i=0;i<Len/2;i++)
    {
        Temp=Data[i];
        Data[i]=Data[Len-i-1];
        Data[Len-i-1]=Temp;
    }
}

void _ShiftN(int Data[],int Len,int N)
{
    _Reverse(Data,Len-N);
    _Reverse(&Data[Len-N],N);
    _Reverse(Data,Len);

}

// perfect shuffle of satisfying [Lenth=3^k-1] 
void _PerfectShuffle(int Data[],int Lenth)
{
    int i=1;

    if(Lenth==2)
    {
        i=Data[Lenth-1];
        Data[Lenth-1]=Data[Lenth-2];
        Data[Lenth-2]=i;
        return;
    }
    while(i<Lenth)
    {
        _Cycle(Data,Lenth,i);
        i=i*3;
    }
}

// look for 3^k that nearnest to N
int _LookUp(int N)
{
    int i=3;
    while(i<=N+1) i*=3;

    if(i>3) i=i/3;

    return i;
}

---

Test:

int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};  
int length = sizeof(arr)/sizeof(int);
in_place_in_shuffle(arr, length);

After this, arr[] will be {0, 5, 1, 6, 2, 7, 3, 8, 4, 9}.

Answer 4

首先，理论：重新排列“排列循环”中的元素。取一个元素并将其放置在新位置，替换当前存在的元素。然后你把那个移位的元素放在新的位置。这会置换另一个元素，因此请冲洗并重复。如果位移的元素属于你第一次开始的元素的位置，你已经完成了一个循环。

实际上，您的问题是我在这里提出的问题的一个特例，即：如何将数组重新排列为 O(N) 时间和 O(1) 空间中的任何给定顺序？在我的问题中，重新排列的位置由一个数字数组描述，其中第 n 个位置的数字指定原始数组中元素的索引。

但是，您的问题中没有这个额外的数组，分配它需要 O(N) 空间。幸运的是，我们可以即时计算此数组中任何元素的值，如下所示：

int rearrange_pos(int x) {
    if (x % 2 == 0) return x / 2;
    else return (x - 1) / 2 + n; // where n is half the size of the total array
}

我不会在这里复制重新排列算法本身；它可以在我的问题的接受答案中找到。

编辑：正如杰森所指出的，我链接到的答案仍然需要分配一个布尔数组，使其成为 O(N) 空间。这是因为一个排列可以由多个循环组成。我一直在尝试消除您的特殊情况对这个数组的需求，但没有成功。似乎没有任何可用的模式。也许其他人可以在这里帮助你。

Answer 5

如果您可以先将数组转换为链表，那么问题就变得微不足道了。