java - 查找数组其余部分中大于每个当前位置的元素的数量

Question

假设我有一个一维数组:

[2, 3, 1, 5, 0, 2]

目标是构造另一个相同长度的数组，其中每个元素表示数组中后续元素中大于当前数量的元素数量(不不同)。所以我的例子的输出是:

[2, 1, 2, 0, 1, 0]

O(n^2) 算法非常简单。对此，什么是更有效的算法(最好是 Java 算法)？

Answer 1

您可以使用 Fenwick tree 在 O(nlogn) 内完成此操作，一种以某种方式保存直方图的数据结构，以便可以在 O(logn) 时间内完成范围查询。

只需以相反的顺序迭代元素并将它们添加到直方图中。

Python 代码:

def fenwick_new(m):
    """Create empty fenwick tree with space for elements in range 0..m"""
    # tree[i] is sum of elements with indexes i&(i+1)..i inclusive
    return [0] * (m+1)

def fenwick_increase(tree,i,delta):
    """Increase value of i-th element in tree by delta"""
    while i < len(tree):
        tree[i] += delta
        i |= i + 1

def fenwick_sum(tree,i):
    """Return sum of elements 0..i inclusive in tree"""
    s = 0
    while i >= 0:
        s += tree[i]
        i &= i + 1
        i -= 1
    return s

def find_bigger(A):
    """Produce an array in which each element denotes the number of subsequent elements that are bigger"""
    top = max(A) + 1
    F = fenwick_new(top)
    B = []
    for n,a in enumerate(A[::-1]):
        count_of_bigger = n - fenwick_sum(F,a) # n is the number of things we have inserted into the tree so far
        B.append(count_of_bigger)
        fenwick_increase(F,a,1)
    return B[::-1]

A=[2,3,1,5,0,2]
print find_bigger(A)

(此算法草图仅在您的输入由具有合理上限的非负整数组成时才有效。如果您有更复杂的输入，请首先使用排序函数计算每个输入元素的排名。)