arrays - 是否可以反转具有恒定额外空间的数组？

Question

假设我有一个数组 A，在 [0, n) 范围内有 n 个唯一元素。换句话说，我有一个整数 [0, n] 的排列。

可以使用 O(1) 额外空间(也称为就地)将 A 转换为 B 使得 B[A[i]] =我?

例如:

       A                  B
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]

Answer 1

是的，这是可能的，使用 O(n^2) 时间算法:

获取索引为 0 的元素，然后将 0 写入该元素索引的单元格。然后使用刚刚覆盖的元素获取下一个索引并在那里写入前一个索引。继续，直到回到索引 0。这是循环领导者算法。

然后从索引 1、2 开始执行相同的操作，...但是在进行任何更改之前执行循环领导者算法，而不从该索引开始进行任何修改。如果此循环包含起始索引下方的任何索引，则跳过它。

---

或者这个 O(n^3) 时间算法:

获取索引为 0 的元素，然后将 0 写入该元素索引的单元格。然后使用刚刚覆盖的元素获取下一个索引并在那里写入前一个索引。继续，直到回到索引 0。

然后从索引 1、2、... 开始执行相同的操作，但在进行任何更改之前，请执行循环领导者算法，而无需从前面的所有索引开始进行任何修改。如果当前索引存在于任何先前的循环中，则跳过它。

---

我写了(稍微优化)implementation C++11 中的 O(n^2) 算法，以确定如果随机排列被反转，每个元素平均需要多少次额外访问。以下是结果:

size accesses
2^10 2.76172
2^12 4.77271
2^14 6.36212
2^16 7.10641
2^18 9.05811
2^20 10.3053
2^22 11.6851
2^24 12.6975
2^26 14.6125
2^28 16.0617

虽然大小呈指数增长，但元素访问的数量几乎呈线性增长，因此随机排列的预期时间复杂度类似于 O(n log n)。