超过人数上限的二进制搜索解决方案 [英] Binary Search solution for Max Number of Surpassers

问题描述

对于整数数组，整数元素的 surpasser 是在其右侧上大于其的元素。

For an array of integers, a surpasser of an integer element is an element on its right hand side that is larger than it.

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

For example, {10,3,4,5,2}, the surpassers of 3 is 4 and 5, and 10 doesn't have any surpasser.

因此，超越者最大数量问题是

给出整数数组

Given an array of integers

输出超出人数的最大值

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

Basically, we need to get the number of surpassers of every element and finally output the max of them.

例如，

{10,3,4,5,2} 的最大超越人数是 2 为 3 有2个超越者。

The max number of surpassers for {10,3,4,5,2} is 2 as 3 has 2 surpassers.

我想知道在使用 binary search 的地方是否存在 O（nLogn）解决方案。

I am wondering whether there is a O(nLogn) solution exists where binary search is used.

我遇到了这个问题，因为本书功能珍珠算法设计说：

I got this question because the chapter 2 in the book Pearls of Functional Algorithm Design says:

在这颗珍珠中，我们解决了Martin Rem
（1988a）的一个小型编程练习。 尽管雷姆（Rem）的解决方案使用二进制搜索，但我们的解决方案是
分而治之的另一种应用。

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.

尽管我有了功能性的解决方案，但我想不出一个用于数组的二进制搜索。

Though I got the functional solution, I can't think of a binary search one for arrays.

有什么想法吗？

推荐答案

解决方案1 ​​

我不知道这是否与Rem的解决方案相同，但是您可以解决此问题

Solution 1

I don't know if this is the same as Rem's solution, but you could solve this quite easily with a binary search tree.

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

Initialize an empty binary search tree and then iterate in reverse order through the array.

将二元搜索树中的每个元素插入，然后对树中所有元素的计数超过该元素的值。 （如果每个子树都存储了它包含的元素数，那么，如果使用了适当的平衡树，则都可以在O（logn）中完成这些操作。）

Insert each element in the binary search tree and then perform a count of all the elements in the tree above the value of the element. (If each subtree stores the number of elements it contains, then these operations can both be done in O(logn) if an appropriate balanced tree is used.)

最大值继任者的数量是由观察到的最大数量给出的。

The max number of successors is given by the largest count observed.

具有类似潜力的可能更快的解决方案基本思想是使用二进制索引树（又名Fenwick树）来存储元素。可以访问此数据结构来检索给定值以上的元素数量，因此可以与解决方案1中的二叉搜索树相同的方式使用。

A potentially faster solution with a similar basic idea is to use a binary indexed tree (aka Fenwick tree) to store the elements. This data structure can be accessed to retrieve the number of elements above a given value so can be used in the same way as the binary search tree in solution 1.

具有与解决方案1相同的O（nlogn）复杂度，但实际上可能会更快，因为它具有较小的内存占用空间。

This will have the same O(nlogn) complexity as solution 1, but may be faster in practice as it has a smaller memory footprint.

这篇关于超过人数上限的二进制搜索解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！