c++ - 以预先指定的顺序随机排列数组变量，而无需使用 “size of input array”的额外内存

输入 :

  A[4] = {0,4,-1,1000} - Actual Array
  P[4] = {1,0,3,2} - Order to be reshuffled

输出:

    A[4] = {4,0,1000,-1}

条件:不要使用其他数组作为内存。可以使用一个或两个额外的变量。

问题:我在C++中具有以下程序，但是对于数组P的某些输入来说，这将失败。

#include<iostream>

using namespace std;

void swap(int *a_r,int *r)
{
    int temp = *r;
    *r = *a_r;
    *a_r = temp;
}
int main()
{
    int A[4] = {0,4,-1,1000};
    int P[4] = {3,0,1,2};
    int value = A[0] , dest = P[0];

    for(int i=0; i<4;i++)
    {
        swap(&A[dest],&value);
        dest = P[dest];
    }
    for(int i=0;i<4;i++)
        cout<<A[i]<<" ";
}

最佳答案

首先，我真的很喜欢 Jonathan 的解决方案，但是我觉得我也可以添加一些有趣的想法。

主要观察到的是P数组由几个循环组成。
让我们考虑p = {1, 4, 3, 2, 0, 5}。一共有三个循环:0 => 1 => 4 => 0，2 => 3 => 2和5 => 5。而要在一个循环中替换变量，我们根本不需要额外的内存。我们只是这样经历

do {
    a[i] = a[p[i]];
    i = p[i];
} while (i != first_i);

(不过，需要特别注意最后一个元素。)完整的工作版本:

    for (int i = 0; i < n; ++i) {
        if (p[i] < 0) {
            // been at index 'i' already
            continue;
        }

        // new loop found
        int j = i;
        int first_value = a[i]; // to be put in last position in the chain
        int prev_j; // we always store previous 'j' index
        do {
            a[j] = a[p[j]];

            prev_j = j;
            j = p[j]; // move to next 'j'
            p[prev_j] = -1; // mark element as processed
        } while (i != j);
        a[prev_j] = first_value;
    }

我的解决方案的唯一问题是它使用p数组将元素标记为“已处理”。有些面试官可能认为还可以，而其他人则不然，这取决于他们所考虑的解决方案。