gpt4 book ai didi

arrays - 使用常量内存在 O(n) 中对 BST 进行排序

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

这不是作业。只是一个有趣的任务:)

给定一个完整的二分查找数组表示的三个。使用常量内存在 O(n) 中对数组进行排序。

例子:

树:

              8
/ \
4 12
/\ / \
2 6 10 14
/\ /\ /\ /\
1 3 5 7 9 11 13 15

数组:8、4、12、2、6、10、14、1、3、5、7、9、11、13、15

输出:1、2、3、4、5、6、7、8、9、10、11、12、13、14、15

最佳答案

有可能,称之为家庭作业的人可能还没有尝试解决它。​​

我们使用以下作为子例程:

Given an array a1 a2 ... an b1 b2 .. bn, convert in O(n) time and O(1) space to

b1 a1 b2 a2 ... bn an

可以在这里找到解决方案:http://arxiv.org/abs/0805.1598

我们使用它如下。

对前 2^(k+1) - 2 个元素执行上述交错操作,从 k=1 开始重复 k=2、3 等,直到经过数组末尾。

例如,在您的数组中,我们得到(由方括号标识的交错集)

 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15   
[ ][ ]

4, 8, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 (k = 1, interleave 2)
[ ][ ]

2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15 (k = 2, interleave 6)
[ ][ ]

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 (k = 3, interleave 14)

所以总时间是 n + n/2 + n/4 + ... = O(n)。使用的空间是 O(1)。

这可以通过归纳证明。

关于arrays - 使用常量内存在 O(n) 中对 BST 进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3158014/

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