c++ - 根据另一个排列数组元素，而不进行复制

Question

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

例如

int a[]={37,43,5,10}; //array to permute
int b[]={3,1,4,2};  //new position of each element

所以一个应该成为

{43,10,37,5}

我自然会考虑制作a的副本，然后在新位置重新分配其元素。但是有没有一种方法而不必复制数组(即更简单的方法)呢？

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

Answer 1

通过一次处理一个排列数组的周​​期，可以在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

数组 b表示我们要进行以下分配链:
a[1] <-- a[3] <-- a[4] <-- a[2] <-- a[1]。

问题在于，在最后一次分配时，我们不再可以访问 a[1](它已被替换为 a[3])。

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

通常，排列可以包含多个周期。处理完一个循环后，我们需要从一个尚未更新的元素开始(即，到目前为止，它还不是循环处理的一部分)。

因此，我们需要知道到目前为止尚未处理哪些元素。

一种可能的方法是临时修改置换 vector 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];
    }
}

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

我将使用此示例在此处显示算法执行的主要步骤:

a = {11, 22, 33, 44}
b = { 2,  1,  4,  3}

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

a = {11, 22, 33, 44}
b = { 2,  1,  4,  3}
aux = 11

步骤2。
我们沿着这个周期，更新元素，将它们标记为已更新(通过消除 b数组中的相应元素)，直到再次到达第一个元素。

a = {22, 22, 33, 44}
b = {-2,  1,  4,  3}
aux = 11

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

a = {22, 11, 33, 44}
b = {-2, -1,  4,  3}
aux = 11

步骤4.
我们继续外循环( for超过 i)。我们看到第二个元素已经被处理(因为 b[1]为负)，因此我们在这里不开始新的循环。我们继续，并从第三个元素(尚未处理)开始一个新的循环。

现在，我们可以重用相同的 aux变量来备份此循环的第一个元素(我们不再需要保留第一个循环的值，因为该循环已被完全解决)。

a = {22, 11, 33, 44}
b = {-2, -1,  4,  3}
aux = 33

步骤5。
第二个循环的处理以前面步骤中描述的类似方式执行，因此结束了:

a = {22, 11, 44, 33}
b = {-2, -1, -4, -3}
aux = 33

步骤6。
继续 i上的循环，没有找到未处理的元素。
现在，我们知道所有元素都已处理，我们可以对 b中的每个元素求反，以恢复原始值。

a = {22, 11, 44, 33}
b = { 2,  1,  4,  3}