发现在阵列的其余部分，其大于所述元件在每个当前位置的元素数 [英] Find the number of elements in the rest of the array that is greater than the element at each current position

问题描述

比方说，我给一个一维数组：

Let's say I am given a one dimensional array:

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

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

的目的是构造相同的长度，其中每个元素表示在大于当前编号的数组在随后的元件元件（未不同）的数目的另一个阵列。所以，在我的情况下，输出将是：

The goal is to construct another array of the same length where each element denotes the number of elements (not distinct) in the subsequent elements in the array that is bigger than the current number. So the output in my case would be:

[2，1，2，0，1，0]

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

这是为O（n ^ 2）算法是pretty的直线前进。还有什么比这更有效的算法（在Java中preferably）这个？

An O(n^2) algorithm is pretty straight forward. What could be a more efficient algorithm (in Java preferably) for this?

推荐答案

您可以在O（nlogn）使用的树状数组，一个数据结构，具有在某种程度上，这样的范围查询可以在O（LOGN）的时间内完成直方图。

You can do this in O(nlogn) using a Fenwick tree, a data structure that holds a histogram in a way such that range queries can be done in O(logn) time.

简单地遍历以相反的顺序的元素，并将它们添加到直方图。

Simply iterate over the elements in reverse order and add them to the histogram.

Python的code：

Python code:

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)

（这种算法草图只会工作，如果你的输入由非负整数，一个合理的上限。如果你有一个更复杂的输入，首先计算使用排序功能的每个输入元素的级别。）

(This algorithm sketch will only work if your input consists of non-negative integers with a reasonable upper bound. If you have a more complicated input, first compute the rank of each input element using a sort function.)

这篇关于发现在阵列的其余部分，其大于所述元件在每个当前位置的元素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！