arrays - 在常量内存空间中应用排列的算法

Question

我看到这题是一本编程面试书，这里我把题简化一下。

假设您有一个长度为 n 的数组 A，并且您有一个长度为 n 的置换数组 P > 同样。您的方法将返回一个数组，其中 A 的元素将按照 P 中指定的索引顺序出现。

简单示例:您的方法采用 A = [a, b, c, d, e] 和 P = [4, 3, 2, 0, 1] .然后它将返回 [e, d, c, a, b]。您只能使用常量空间(即您不能分配另一个数组，它占用 O(n) 空间)。

想法？

Answer 1

有一个简单的 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) 时间。

您可以通过以下方式存储正确位置的信息:

1. 将P中对应的表项设置为-1，不可恢复:经过以上操作，P将变为[-1, -1, 2, -1, -1] , 这表示只有第二个可能不在正确的位置，进一步的步骤将确保它在正确的位置并终止算法；

2. 将P中对应的条目设置为-n - 1:P变为[-5, -4, 2, -1, -2],可以在 O(n) 中轻松恢复。