Перестановка массива с заданным порядком без создания копии массива или изменения порядка

Question

Я уже нашел почти тот же вопрос, заданный здесь. Но мне нужно сделать это немного сложнее.

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

int[] a = {5, 35, 7, 2, 7};
int[] order = {3, 0, 2, 4, 1};

После того, как алгоритм a должен выглядеть следующим образом:

a = {2, 5, 7, 7, 35};

Порядок именованного массива ни в коем случае нельзя изменять, и все копии массива запрещены. Допускаются только постоянные переменные, такие как нормальное целое число.

Обратите внимание, что эта проблема не связана с конкретным языком. Это должно быть на языке, подобном псевдокоду. Просто понятно.

Так у кого-нибудь здесь есть идея? Я сижу перед этой проблемой в течение 3 дней и надеюсь получить некоторую помощь, потому что я думаю, что я действительно застрял сейчас.

Заранее спасибо.

Answer 1

Учитывая указанные диапазоны чисел, вы можете:

• Добавить 100 раз соответствующее значение заказа для каждого элемента.
• Сортировать.
• Заменитькаждый элемент по элементу по модулю 100.

Немного Python:

a = [5, 35, 7, 2, 7]
order = [3, 0, 2, 4, 1]

mult = max(a) + 1
a = [a_item + order_item * mult
     for a_item, order_item in zip(a, order)]
a.sort(reverse=True)
a = [a_item % mult for a_item in a]

print(a)    # [2, 5, 7, 7, 35]

Я должен подчеркнуть, что он работает для показанных чисел;негативы и соображения переполнения могут ограничивать более общую применимость.

Answer 2

Перестановка, определяемая order, состоит из одного или нескольких циклов. Применять один цикл к массиву a несложно, но задача состоит в том, чтобы каким-то образом узнать, какие элементы массива принадлежат циклу, который вы уже обработали таким образом. Если есть способ пометить посещенных элементов, например, с помощью дополнительного бита, то эта проблема решена. Но использование дополнительного бита является сокрытием для массива с дополнительными данными. Так что это должно быть исключено.

Когда нет возможности выполнить такую ​​маркировку, тогда все еще есть выход: выполнять операцию цикла над массивом a только когда вы находитесь в крайнем левом индексеэтот цикл (или самый правый). Недостатком является то, что в каждом индексе вам нужно пройти цикл, к которому принадлежит индекс, чтобы проверить, действительно ли вы находитесь в его левом крайнем положении или нет. Это означает, что вы будете повторять один и тот же цикл несколько раз.

Вот как это выглядит в JavaScript:

function isLeftOfCycle(order, i) {
    let j = order[i]; 
    while (j > i) {
        j = order[j];
    }
    return (j === i); // a boolean
}

function applyCycle(arr, order, i) {
    let temp = arr[i];
    let k = i;
    let j = order[i];
    while (j > i) {
        arr[k] = arr[j];
        k = j;
        j = order[j];
    }
    arr[k] = temp;
}

function sort(a, order) {
    for (let i = 0; i < order.length; i++) {
        if (isLeftOfCycle(order, i)) {
            applyCycle(a, order, i);
        }
    }
}

// Example run:
let a = [5, 35, 7, 2, 7];
let order = [3, 0, 2, 4, 1];
sort(a, order);
console.log(a);

Очевидно, что это имеет цену: сложность времени больше не O (n) , а O (n²) .