gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:24:37 26 4
gpt4 key购买 nike

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

假设您有一个长度为 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) 时间。

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

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

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

关于arrays - 在常量内存空间中应用排列的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16501424/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com