是否可以使用恒定的额外空间反转数组？

Question

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

是否可以使用O(1)额外空间(原位AKA)将A转换为B,使得B [A [i]] = 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开始做同样的事情......但是在进行任何更改之前执行循环引导算法而不需要从所有前面的索引开始进行任何修改.如果任何前一个周期中存在当前索引,则跳过它.

我已经写(略优化)执行在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).