Перестановка вектора

Question

предположим, что у меня есть вектор:

 0  1  2  3  4  5
[45,89,22,31,23,76]

И перестановка его индексов:

[5,3,2,1,0,4]

Есть ли эффективный способ применить его в соответствии с перестановкой, получив таким образом:

[76,31,22,89,45,23]

Используете не более O(1) дополнительного пространства?

Answer 1

Да.Начиная с крайнего левого положения, ставим элемент там всё правильно позиция i, заменив его (другим) неуместным элементом в этой позиции i.Здесь нам понадобится дополнительное пространство O(1).Мы продолжаем менять местами пары элементов, пока элемент в этой позиции не станет правильным.Только после этого переходим к следующей позиции и делаем то же самое.

Пример:

[5 3 2 1 0 4] исходное состояние

[4 3 2 1 0 5] заменены (5,4), 5 теперь находится в правильном положении, но 4 по-прежнему неверно

[0 3 2 1 4 5] поменялись местами (4,0), теперь и 4, и 0 находятся в правильных позициях, переходим к следующей позиции

[0 1 2 3 4 5] поменялись местами (3,1), теперь 1 и 3 находятся в правильных позициях, переходим к следующей позиции

[0 1 2 3 4 5] все элементы находятся в правильных позициях, конец.

Примечание:

Поскольку каждая операция замены помещает хотя бы один (из двух) элементов в правильную позицию, нам понадобится не более N таких замен.

Answer 2

Решение Зака ​​очень хорошее.

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

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

Например:

a = [45,89,22,31,23,76];
b = [5,3,2,1,0,4]

Теперь, если вы хотите просмотреть значения в а, вы можете сделать что-то вроде (псевдокод):

for i=0 to 4
{
    process(a[i]);
}

Если вы хотите перебрать значения в новом порядке, выполните:

for i=0 to 4
{
    process(a[b[i]]);
}

Как упоминалось ранее, во многих случаях этого решения может быть достаточно, но в некоторых других — нет.В других случаях вы можете использовать решение Зака. Но для случаев, когда это решение можно использовать, оно лучше, потому что сортировка вообще не требуется.