如何解决BST问题?

维杰

给我这个问题:

系统会为您提供n个不同整数a0,a1,...的序列。an-1。在每次迭代中,您选择一个最大数目并将其删除,确定最大数目的成本就是该数目左边的数字。重复此n次。给定ai的实现,可以使用O(n log n)算法来计算n次迭代的总成本。

我知道我们必须使用BST来解决此问题,因为它是O(N log N),但是,我不确定该怎么做。

我当时以为可以将值和索引存储在hashMap中,当删除操作完成后,我们在BST中搜索该索引,然后在遍历的路径中添加索引值。但是,在删除节点时,我们必须为所有要删除的索引减小BST索引值。

我不确定这是否可行,并且我很乐意为此提供任何建议/指导:)

用户名

尽管@ 0x499602D2注释正确,但排序是正确的方法。这个问题是合并排序的另一个应用,类似于计数反转。

从右边合并元素会减少剩余元素的数量,从而降低成本(您知道为什么吗?)。数组完全排序后,成本降低到0。

我希望这足以让您入门。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章