algorithm - 最大数量的超越者的二进制搜索解决方案

Question

对于整数数组，整数元素的超越者 是其右侧 大于它的元素。

例如{10,3,4,5,2}，3的超越者是4和5 ，10没有任何超越者。

所以最大超越者数问题是

Given an array of integers

Out put the max number of surpassers

基本上，我们需要获取每个元素的超越者数量，最后输出它们的最大值。

例如，

{10,3,4,5,2} 的最大超越者数量为 2，因为 3 有 2 个超越者。

---

我想知道在使用二进制搜索 的地方是否存在O(nLogn) 解决方案。

我得到这个问题是因为书的第 2 章 Pearls of Functional Algorithm Design说:

In this pearl we solve a small programming exercise of Martin Rem (1988a). While Rem’s solution uses binary search, our solution is another application of divide and conquer.

虽然我得到了函数式解决方案，但我想不出数组的二分查找。

有什么想法吗？

Answer 1

方案一

我不知道这是否与 Rem 的解决方案相同，但您可以使用二叉搜索树轻松解决此问题。

初始化一个空的二叉搜索树，然后以相反的顺序遍历数组。

将每个元素插入二叉搜索树中，然后对树中元素值以上的所有元素进行计数。 (如果每个子树存储它包含的元素的数量，那么如果使用适当的平衡树，那么这些操作都可以在 O(logn) 中完成。)

后继者的最大数量由观察到的最大计数给出。

解决方案2

具有类似基本思想的可能更快的解决方案是使用二叉索引树(又名 Fenwick 树)来存储元素。可以访问此数据结构以检索高于给定值的元素数，因此可以像解决方案 1 中的二叉搜索树一样使用。

这将具有与解决方案 1 相同的 O(nlogn) 复杂性，但在实践中可能更快，因为它占用的内存更小。