我看到这题是一本编程面试书,这里我把题简化一下。
假设您有一个长度为 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)
空间)。
想法?
最佳答案
有一个简单的 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) 中轻松恢复。
关于arrays - 在常量内存空间中应用排列的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16501424/