根据另一个排列数组元素,而不进行复制

Gia*_*epo 1 c++ arrays algorithm permutation

考虑一个数组。根据另一个提供元素新位置的数组(不先复制该数组的副本),将其元素置换的好方法是什么?

例如

int a[]={37,43,5,10}; //array to permute
int b[]={3,1,4,2};  //new position of each element
Run Code Online (Sandbox Code Playgroud)

所以一个应该成为

{43,10,37,5}
Run Code Online (Sandbox Code Playgroud)

我自然想到了制作a的副本,然后在新位置重新分配其元素。但是有没有一种方法可以不复制数组(即更简单的方法)呢?

注意:如果可能的话,不应使用特定的C ++标头,而应仅使用<iostream>

qwe*_*man 8

通过一次处理一个置换数组的周期,可以在 O(n) 时间内使用 O(1) 额外内存完成。

注意:此方法比此特定设置所需的更复杂(a并且b都是 int 数组),但它有一些好处:

  • 它可以处理任意数据类型(例如,置换数组a可以是字符串数组)。

  • 它可以保留b置换数组中的原始值。


考虑最初的例子:

int a[] = {37, 43, 5, 10};  // array to permute
int b[] = { 3,  1, 4,  2};  // new position of each element
Run Code Online (Sandbox Code Playgroud)

该数组b表明我们要进行以下分配链:

a[1] <-- a[3] <-- a[4] <-- a[2] <-- a[1].

问题是在最后一次分配中,我们不再具有访问权限a[1](它已被替换为a[3])。

然而,起始元素的原始值可以保存在一个辅助变量中,以便我们在关闭循环时使用它(保证当我们关闭循环时,我们将精确到达我们开始的元素 - 否则某些元素可以通过多种方式访问​​,即我们将有 b[i] = b[j]),对于某些 i != j)。


一般来说,排列可能包含多个循环。在处理完一个循环之后,我们需要从一个尚未更新的元素开始(即它目前不是循环处理的一部分)。

因此,我们需要知道到目前为止哪些元素没有被处理。

一种可能的方法是临时修改置换向量b以跟踪更新了哪些元素,例如,b在更新 中的元素时取消相应位置中的值a。这样做的好处是最后,我们可以遍历所有元素b并恢复初始值(通过再次否定所有元素)。


下面是之前的想法的实现。

int main() {
    int a[] = {11, 22, 33, 44};
    int b[] = { 2,  1,  4,  3};
    int aux, crtIdx, nxtIdx;

    int n = sizeof(a) / sizeof(a[0]);

    for (int i = 0; i < n; i++) {
        // check whether the i'th element
        // was already processed
        if (b[i] < 0) {
            continue;
        }

        // start processing of a new cycle;
        // backup the first value to aux
        aux = a[i];
        crtIdx = i;
        nxtIdx = b[i] - 1;

        // advance along the cycle until we reach 
        // again the first element 
        while (nxtIdx != i) {
            a[crtIdx] = a[nxtIdx];

            // use the b array to mark that the 
            // element at crtIdx was updated
            b[crtIdx] = -b[crtIdx];

            crtIdx = nxtIdx;
            nxtIdx = b[nxtIdx] - 1;
        }

        // finalize the cycle using the aux variable
        a[crtIdx] = aux;
        b[crtIdx] = -b[crtIdx];
    }

    // restore the original values of b[i]
    for (int i = 0; i < n; i++) {
        b[i] = -b[i];
    }
}
Run Code Online (Sandbox Code Playgroud)

注意:虽然代码包含两个嵌套循环,但时间复杂度为 O(n)。考虑到每个元素只更新一次这一事实可以看出这一点(如果我们到达一个已经处理过的元素,则立即继续外部循环)。


我将在这里展示算法执行的主要步骤,使用这个例子:

a = {11, 22, 33, 44}
b = { 2,  1,  4,  3}
Run Code Online (Sandbox Code Playgroud)

步骤 1. 我们查看第一个元素(请查看代码中的外部for循环i)。第一个元素不是已处理循环的一部分,因此我们开始处理新循环。我们通过存储aux这个元素的初始值来实现。

a = {11, 22, 33, 44}
b = { 2,  1,  4,  3}
aux = 11
Run Code Online (Sandbox Code Playgroud)

第 2 步。 我们继续这个循环,更新元素,将它们标记为已更新(通过否定b数组中的相应元素),直到我们再次到达第一个元素。

a = {22, 22, 33, 44}
b = {-2,  1,  4,  3}
aux = 11
Run Code Online (Sandbox Code Playgroud)

第 3 步。 我们再次到达循环的第一个元素,需要它的初始值来更新循环的最后一个元素。这是我们使用辅助变量的地方。这样,第一个循环就完成了。

a = {22, 11, 33, 44}
b = {-2, -1,  4,  3}
aux = 11
Run Code Online (Sandbox Code Playgroud)

第 4 步。 我们继续外循环(forover i)。我们看到第二个元素已经被处理(因为b[1]是负数),因此我们不会在这里开始一个新的循环。我们继续,并在第三个元素(尚未处理)处开始一个新循环。

现在我们可以重用相同的aux变量来备份这个循环的第一个元素(我们不再需要保存第一个循环的值,因为那个循环已经完全解决了)。

a = {22, 11, 33, 44}
b = {-2, -1,  4,  3}
aux = 33
Run Code Online (Sandbox Code Playgroud)

步骤5. 第二个循环的处理以前面步骤中描述的类似方式进行,结果是这样的:

a = {22, 11, 44, 33}
b = {-2, -1, -4, -3}
aux = 33
Run Code Online (Sandbox Code Playgroud)

第六步 ,循环i继续,没有发现未处理的元素。现在,我们知道所有元素都被处理了,我们可以否定每个元素b以恢复原始值。

a = {22, 11, 44, 33}
b = { 2,  1,  4,  3}
Run Code Online (Sandbox Code Playgroud)


Sco*_*ica 5

最简单的答案是复制a到b,并随即销毁b:

for (i = 0; i < B_SIZE; ++i):
    b[i] = a[b[i] - 1];
Run Code Online (Sandbox Code Playgroud)

然后,如果需要,只需复制b回a:

for (i = 0; i < B_SIZE; ++i):
    a[i] = b[i];
Run Code Online (Sandbox Code Playgroud)

由于a和b都是int数组,因此您不会浪费任何多余的内存。您以中的正确值结束a,而没有使用比给您的内存更多的内存。这不是最大效率(尽管它是O(n)),但是最容易理解。