向量置换

对。从最左边的位置开始,我们把 要素 这是正确的 位置 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个这样的交换。

Zach的解决方案非常好。

尽管如此,我还是想知道为什么需要排序。如果你有索引的排列,就把这些值作为指向旧数组的指针。

这可以消除首先对数组进行排序的需要。这不是一个可以在所有情况下使用的解决方案,但在大多数情况下它都能很好地工作。

例如:

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

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