在恒定存储空间中应用置换的算法
问题内容：
我看到这个问题是一本编程访谈书，在这里我正在简化这个问题。
假设您有一个Alength 的数组n，并且您也有一个Plength
的排列数组n。您的方法将返回一个数组，其中的元素A将按在中指定的索引顺序出现P。
快速示例：您的方法采用A = [a, b, c, d, e]和P = [4, 3, 2, 0, 1]。然后它将返回[e, d, c, a, b]。您只能使用恒定的空间（即您不能分配占用O(n)空间的另一个数组）。
有想法吗？
问题答案：
有一个简单的O（n ^ 2）算法，但是您可以在O（n）中执行此操作。例如：
A = [a，b，c，d，e]
P = [4，3，2，0，1]
我们可以将每个元素交换A为所需的正确元素P，每次交换之后，在正确的位置将再有一个元素，并针对每个位置以循环方式进行此操作（以^s
指向的交换元素）：
[a, b, c, d, e] <- P[0] = 4 != 0 (where a initially was), swap 0 (where a is) with 4
^ ^
[e, b, c, d, a] <- P[4] = 1 != 0 (where a initially was), swap 4 (where a is) with 1
^ ^
[e, a, c, d, b] <- P[1] = 3 != 0 (where a initially was), swap 1 (where a is) with 3
^ ^
[e, d, c, a, b] <- P[3] = 0 == 0 (where a initially was), finish step
经过一圈后，我们在数组中找到了下一个不在正确位置的元素，然后再次执行此操作。因此，最终您将获得所需的结果，并且由于每个位置都被触摸了恒定的时间（对于每个位置，最多执行一次操作（交换）），因此时间为O（n）。
您可以通过以下方式存储正确位置的信息：
-
将P中的对应条目设置为-1，这是不可恢复的：完成上述操作后，P将变为
[-1, -1, 2, -1, -1]，这表示只有第二个可能不在正确的位置，并且下一步将确保它在正确的位置定位并终止算法； -
将P中的相应条目设置为
-n - 1：P变为[-5, -4, 2, -1, -2]，可以在O（n）中轻松恢复。
