给定数组和键,在左右子数组中找到小于或等于自身的元素数量？

Question

我必须i在左右子阵列中找到小于或等于数组元素的元素数.

例如,如果我的数组是

A[]=4 3 5 2 2 5

我的2个数组将是

0 0 2 0 0 5

和

3 2 3 1 1 0

i第一个数组的第th个元素表示小于或等于i第-th个元素左边第-t个元素的元素个数i.

i第二个数组的第th个元素表示小于或等于i第-th个元素右侧第 - 个元素的元素个数i.

我可以使用两个循环在O(n ²)中找到这些数组.

这可以在O(n)中完成吗？

Answer 1

您可以使用Fenwick树在O(nlogm)(其中n是A的长度,m是数组中最大元素的大小)中执行此操作.

Fenwick树(也称为二进制索引树)允许您向数组添加元素,并在O(logn)时间内计算连续元素的总和.topcoder上有一个很好的教程.

在这个问题中,我们可以使用Fenwick树来存储我们看到每个值的次数的直方图.直方图开始为空,然后我们逐渐将元素插入直方图.

所以我们需要遍历数组,每次首先计算有多少元素的值小于当前值,然后将当前值添加到数组中.

Python代码:

def find_lower(A):
    """Return B where B[i] is the number of elements <= A[i] in A[0:i]"""
    top = max(A) + 1
    F = fenwick_new(top)
    left = []
    for a in A:
        left.append( fenwick_sum(F,a) )
        fenwick_increase(F,a,1)
    return left

A=[4, 3, 5, 2, 2, 5]
print find_lower(A)
print find_lower(A[::-1])[::-1]

这使用了一些标准的Fenwick树函数:

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

Answer 2

不，不可能及时完成O(n)。你能做的最好的就是O(n log n)。

这是证据。假设原始数组具有n 不同的元素。让我们计算出您想要的第一个数组有多少种可能性（另一个数组的证明类似）。第一个数字 ( ) 有 1 种可能性0。第二个数字有 2 种可能性（0或1）。第三个数字有 3 种可能（0、1或2），依此类推。由此可见，最多1 * 2 * 3 * ... * n = n!有可能的答案。事实上，很容易看出，对于每个可能的答案，至少有一组不同的数字来产生它（从左到右工作。如果是answer[i]，0则设置original[i]为小于所有先前选择的数字。如果answer[i]是为i，设置original[i]为大于所有先前选择的数字。否则，设置original[i]为介于i第 最小和(i+1)已选择的第 最小数字之间的数字。任何算法都必须确定哪一个n!可能的答案是正确的。如果我们总是可以通过比较来完成算法，f(n)那么2^f(n) >= n!（每次比较只有 2 个可能的结果，因为原始数字都是不同的）。取双方的对数（以 2 为底），我们得到f(n) >= log(n!)。使用斯特林近似，log(n!)我们发现我们无法比比较做得更好O(n log n)。

及时去做是可以的O(n log n)。以下 Java 方法（未及时运行O(n log n)）返回您需要的第一个数组（第二个数组也可以类似地完成）。Arrays.sort()使用 TimSort ，它是O(n log n). 但是，为了使整个方法能够及时运行O(n log n)，你必须替换为where 方法ArrayList的实现，并且全部及时运行。根据http://www.nayuki.io/page/avl-tree-list，确实和及时，并且可以“增强” an以便搜索也是如此。这证明你的数组可以及时找到。Listadd(Object object)remove(int index)lastIndexOf(Object object)O(log n)AvlTreeListadd()remove()O(log n)AvlTreeListO(log n)O(n log n)

public static int[] firstArray(int[] arr) {
    int[] copy = arr.clone();
    Arrays.sort(copy);
    List<Integer> list = new ArrayList<>();
    for (int a : copy)
        list.add(a);
    int length = arr.length;        
    int[] temp = new int[length];
    for (int i = length - 1; i >= 0; i--) {
        int j = list.lastIndexOf(arr[i]);
        temp[i] = j;
        list.remove(j);
    }
    return temp;
}