矢量的排列

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]

现在,如果你想要删除a中的值,你可以做类似的事情(伪代码):

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

如果要循环新订单中的值,请执行以下操作:

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

如前所述,在许多情况下,这种解决方案可能已足够,但在某些其他情况下可能不会.对于其他情况,您可以使用Zach.But的解决方案,对于可以使用此解决方案的情况,它更好,因为根本不需要排序.