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

Question

对于整数数组，整数元素的surpasser是其右侧大于它的元素.

例如{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) 解决方案。

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

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

解决方案 1

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

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

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

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

解决方案 2

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

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

Answer 2

这是一个使用二进制搜索的解决方案，但我认为这不是您要查找的内容（二进制搜索不是该算法中使用的主要技术）。此解决方案的大部分工作是通过排序和 Fenwick 树的组合来完成的。二分搜索组件可能可以用哈希映射或二分搜索树代替。

无论如何，这是代码。如果您有任何问题，请告诉我：

import java.util.Arrays;

public class MaxSurpassersFenwick {
    public static void main(String[] args) {
        // The number of surpassers for a value is the number of values to the right and bigger.
        // The number of surpassers for { 2, 7, 5, 5, 2, 7, 0, 8, 1 } are { 5, 1, 2, 2, 2, 1, 2, 0, 0 }.
        // The max number of surpassers is thus 5.
        // The code I have written runs in O(n lg n) time.

        int[] values = new int[] { 2, 7, 5, 5, 2, 7, 0, 8, 1 };

        System.out.println("The max number of surpassers for any value in " + Arrays.toString(values) + " is " + getMaxNumSurpassers(values) + ".");
    }

    public static int getMaxNumSurpassers(int[] values) {
        if (values == null) {
            throw new IllegalArgumentException("Array of values cannot be null!");
        }

        int n = values.length;

        if (n <= 1) {
            return 0;
        }

        int[] numSurpassers = getNumSurpassers(values);
        int maxNumSurpassers = numSurpassers[0];

        for (int i = 1; i < n; ++i) {
            maxNumSurpassers = Math.max(maxNumSurpassers, numSurpassers[i]);
        }

        return maxNumSurpassers;
    }

    public static int[] getNumSurpassers(int[] values) {
        if (values == null) {
            throw new IllegalArgumentException("Array of values cannot be null!");
        }

        int n = values.length;
        int[] sortedValues = values.clone();
        FenwickTree numValues = new FenwickTree(n);
        int[] numSurpassers = new int[n];

        Arrays.sort(sortedValues);

        // Iterate through the values from right to left
        for (int i = n - 1; i >= 0; --i) {
            // Find the index of the current value in the sorted array of values
            // If the value occurs more than once, return the last index for that value
            int lastOccurrenceIndex = binarySearchLastOccurrence(sortedValues, values[i]);

            // Count the number of values we've seen that are greater than the current value
            numSurpassers[i] = numValues.sum(lastOccurrenceIndex + 1, n - 1);

            // Mark the current value as seen
            numValues.add(lastOccurrenceIndex, 1);
        }

        return numSurpassers;
    }

    private static int binarySearchLastOccurrence(int[] values, int valueToFind) {
        int low = 0;
        int high = values.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (mid == high || (values[mid] == valueToFind && values[mid] < values[mid + 1])) {
                return mid;
            } else if (values[mid] > valueToFind) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }

    private static class FenwickTree {
        private int size;
        private int[] values;

        public FenwickTree(int size) {
            this.size = size;
            this.values = new int[size];
        }

        public void add(int index, int value) {
            while (index < this.size) {
                this.values[index] += value;
                index |= index + 1;
            }
        }

        public int prefixSum(int index) {
            int sum = 0;
            int n = index + 1;

            while (n > 0) {
                sum += this.values[n - 1];
                n &= n - 1;
            }

            return sum;
        }

        public int sum(int leftIndex, int rightIndex) {
            if (leftIndex > rightIndex) {
                return 0;
            }

            int rightSum = this.prefixSum(rightIndex);
            int leftSum = (leftIndex > 0) ? this.prefixSum(leftIndex - 1) : 0;

            return (rightSum - leftSum);
        }
    }
}

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

Binary Search solution for Max Number of Surpassers

algorithm

binary-search

解决方案 1

解决方案 2