给我这个问题:
系统会为您提供n个不同整数a0,a1,...的序列。。。an-1。在每次迭代中,您选择一个最大数目并将其删除,确定最大数目的成本就是该数目左边的数字。重复此n次。给定ai的实现,可以使用O(n log n)算法来计算n次迭代的总成本。
我知道我们必须使用BST来解决此问题,因为它是O(N log N),但是,我不确定该怎么做。
我当时以为可以将值和索引存储在hashMap中,当删除操作完成后,我们在BST中搜索该索引,然后在遍历的路径中添加索引值。但是,在删除节点时,我们必须为所有要删除的索引减小BST索引值。
我不确定这是否可行,并且我很乐意为此提供任何建议/指导:)
尽管@ 0x499602D2注释正确,但排序是正确的方法。这个问题是合并排序的另一个应用,类似于计数反转。
从右边合并元素会减少剩余元素的数量,从而降低成本(您知道为什么吗?)。数组完全排序后,成本降低到0。
我希望这足以让您入门。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句