是否有可能反转恒额外的空间阵列？ [英] Is it possible to invert an array with constant extra space?

问题描述

比方说，我有一个数组的 A 的用的 N 的独特的范围内的 [0，n）的元素的。换句话说，我有整数[0的排列，N）。

时可能转化的 A 的成的乙的使用O（1）额外的空间（又名就地）这样的苯并[a [i] = I 的？

例如：

  A B
[3，1,0，2,4]  -  GT; [2，1，3,0，4]
 

解决方案

是的，这是可能的，为O（n ^ 2）时间的算法：

考虑元素在索引0，然后写0到该元素索引的细胞。然后使用仅覆盖了元素得到下一个索引并写入previous指数在那里。继续，直到你回去指数0。这是循环的领导者的算法。

然后做同一起跑线从指数1，2，...但在做之前，任何更改，而从这个指数开始任何修改执行周期领先算法。如果这个周期包含起始索引下的任何指标，只是跳过它。

---

还是这为O（n ^ 3）时间的算法：

考虑元素在索引0，然后写0到该元素索引的细胞。然后使用仅覆盖了元素得到下一个索引并写入previous指数在那里。继续，直到你回到索引0。

然后做同一起跑线从指数1，2，...但在做之前，任何更改，而所有preceding指标开始任何修改执行周期领先算法。如果目前的指数在任何preceding周期present，只是跳过它。

---

我写的O（略优化）实施（N ^ 2）算法在C ++ 11来确定多少额外的访问所需的平均每个元素如果随机排列被反转。下面是结果：

 尺寸访问
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）的。

Let's say I have an array A with n unique elements on the range [0, n). In other words, I have a permutation of the integers [0, n).

Is possible to transform A into B using O(1) extra space (AKA in-place) such that B[A[i]] = i?

For example:

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

解决方案

Yes, it is possible, with O(n^2) time algorithm:

Take element at index 0, then write 0 to the cell indexed by that element. Then use just overwritten element to get next index and write previous index there. Continue until you go back to index 0. This is cycle leader algorithm.

Then do the same starting from index 1, 2, ... But before doing any changes perform cycle leader algorithm without any modifications starting from this index. If this cycle contains any index below the starting index, just skip it.

---

Or this O(n^3) time algorithm:

Take element at index 0, then write 0 to the cell indexed by that element. Then use just overwritten element to get next index and write previous index there. Continue until you go back to index 0.

Then do the same starting from index 1, 2, ... But before doing any changes perform cycle leader algorithm without any modifications starting from all preceding indexes. If current index is present in any preceding cycle, just skip it.

---

I have written (slightly optimized) implementation of O(n^2) algorithm in C++11 to determine how many additional accesses are needed for each element on average if random permutation is inverted. Here are the results:

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

While size grows exponentially, number of element accesses grows almost linearly, so expected time complexity for random permutations is something like O(n log n).

这篇关于是否有可能反转恒额外的空间阵列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！