向量的置换

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

如前所述，这soluion可能是在许多情况下足够了，但可能无法在某些其他情况下。对于其他情况下可以使用由Zach.But用于箱子的解决方案，其中该溶液可以使用，最好是，因为需要完全没有分选。