Перемешивать переменные массива в предварительно заданном порядке, без использования дополнительной памяти «размера входного массива»

Question

Ввод:

  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]<<" ";
}

Answer 1

Так как у вас есть запасной массив с именем P, и в предложенном вопросе нет ничего, что указывало бы, что он должен рассматриваться как постоянный массив, вы можете сделать:

for (i = 0; i < 4; i++)
    P[i] = A[P[i]];
for (i = 0; i < 4; i++)
    A[i] = P[i];

Если вам не разрешено изменять P, вам придется работать намного усерднее (и вам также придется работать намного больше, если тип данных A не совпадает или не совместим с типом P).

Тем не менее, я боюсь, что это хитрость ловкости рук, которая на самом деле не отвечает на вопрос;он выполняет свою работу, но не отвечает на вопрос.

Answer 2

int _tmain(int argc, _TCHAR* argv[])
{
    A[4] = {0,4,-1,1000}
    P[4] = {1,0,3,2}
    int temp = arr2[0];

    for(int i=0;i<4;i++)
    {
        for(temp = P[i];i<3;temp = P[temp])
        {
        if(temp >= i)
        {
            int data; 
            data = A[i];
            A[i] = A[temp];
            A[temp] = data;
            break;
        }
        }

    }
    _getch();
    return 1;
}

Answer 3

int _tmain(int argc, _TCHAR* argv[])
{
    A[4] = {0,4,-1,1000}
    P[4] = {1,0,3,2}
    int temp = arr2[0];

    for(int i=0;i<4;i++)
    {
        for(temp = P[i];i<3;temp = P[temp])
        {
        if(temp >= i)
        {
            int data; 
            data = A[i];
            A[i] = A[temp];
            A[temp] = data;
            break;
        }
        }

    }
    _getch();
    return 1;
}

Answer 4

Прежде всего, мне действительно нравится решение Джонатана , но я чувствую, что могу добавить и некоторые интересные идеи.

Основное наблюдение состоит в том, что массив 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, чтобы пометить элемент как «обработанный».Некоторые интервьюеры могут считать это нормальным, другие - нет, в зависимости от решения, которое они имеют в виду.

Answer 5

Можно утверждать, что это идет вразрез с духом вопроса - но может использовать несколько экземпляров стека (с точки зрения времени выполнения) одной локальной переменной (с точки зрения кода). То, что ему позволено мутировать P, столь же неуверенно, поэтому FWIW - рекурсивный ответ ...

template <int N>
void shuffle(int (&a)[N], int p[], int i = -1)
{
    if (++i < N)
    {
        int result = a[p[i]];
        shuffle(a, p, i);
        a[i] = result;
    }
}

Answer 6

Слегка изменено для вычисления значения dest

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-1;i++)
    {
      int count=0;
      dest = P[i];
      while(dest<i){ //if P[i] points to lower value, it got swapped with some other position. 
        dest = P[dest];
      }
      swap(&A[dest],&A[i]);
    }
    for(int i=0;i<4;i++)
        cout<<A[i]<<" ";
    cout<<"\n";
}