Jac*_*ale 6 algorithm binary-search
对于整数数组,整数元素的超越者是其右侧比它大的元素.
例如,{10,3,4,5,2}超越者3是4和5,并且10没有任何超越者.
所以最大超越数量问题是
给定一个整数数组
超出最大数量的超越者
基本上,我们需要获得每个元素的超越数量,最后输出它们的最大值.
例如,
surpassers的最大数量{10,3,4,5,2}为2的3有2个surpassers.
我想知道是否O(nLogn)存在使用二进制搜索的解决方案.
我得到了这个问题,因为" 功能算法设计珍珠 "一书中的第2章说:
在这颗珍珠中,我们解决了Martin Rem(1988a)的一个小编程练习.虽然Rem的解决方案使用二分搜索,但我们的解决方案是另一种分而治之的应用.
虽然我得到了功能解决方案,但我想不出一个二进制搜索数组.
有任何想法吗？
我不知道这是否与Rem的解决方案相同,但您可以使用二叉搜索树轻松解决这个问题.
初始化一个空的二进制搜索树,然后以相反的顺序迭代通过该数组.
在二叉搜索树中插入每个元素,然后对元素值上方的树中的所有元素执行计数.(如果每个子树存储它包含的元素数,那么如果使用适当的平衡树,则这些操作都可以在O(logn)中完成.)
最大连续数由观察到的最大计数给出.
具有类似基本思想的潜在更快的解决方案是使用二进制索引树(也称为Fenwick树)来存储元素.可以访问此数据结构以检索给定值以上的元素数,因此可以与解决方案1中的二叉搜索树相同的方式使用.
这将具有与解决方案1相同的O(nlogn)复杂度,但在实践中可能更快,因为它具有更小的内存占用.