计算数组位置的越来越小的值

I have the following problem I need to optimize. For a given array(with duplicated keys allowed), for each position i in the array, I need to compute all bigger values right of i, and all smaller values left of i. If we have:

我有以下问题需要优化。对于给定的数组(允许重复键)，对于数组中的每个位置i，我需要计算i右边的所有大值，以及i左边的所有小值。

1 1 4 3 5 6 7 and i = 3(value 3), the count of smaller values to left of i is 1(no repeated keys), and to the right, the number of bigger values is 3.

1 1 4 3 5 6 7和i = 3(值3)，i左边的小值数为1(无重复键)，右边的大值数为3。

The brute force solution of this problem is ~N^2, and with some extra space I can manage to compute the smaller values from the bigger ones, so reducing complexity to ~(N^2)/2. My question is: is there a faster way to get it done? Maybe NlgN? I imagine there is a data structure out there I don't know which will allow me to do the computation faster.

的蛮力解决这个问题~ N ^ 2,和一些额外的空间我可以设法从更大的计算值越小,所以降低复杂度~(N ^ 2)/ 2。我的问题是:有没有更快的方法来完成它?也许NlgN ?我想象有一个数据结构我不知道它能让我更快地计算。

EDIT: Thank you all for your replies and discussions. You can find two good solutions two the problem below. Always a pleasure learning from developers in *.

编辑:谢谢大家的回复和讨论。你可以找到两个很好的解决方案，两个问题如下。在*上向开发人员学习总是一件愉快的事。

4 个解决方案

#1

You asked for O(n log n), here I give you technically an O(n) solution.

你要求O(n log n)这里我技术上给你一个O(n)解。

As hinted by @SayonjiNakate, the solution using segment tree (I used Fenwick tree in my implementation) runs in O(n log M) time, where M is the maximum possible value in the array. Assuming M is constant (hey it's bounded by the size of int!), the algorithm runs in O(n). Sorry if you feel that I'm cheating in reporting the complexity, but hey, technically that's true! =D

正如@SayonjiNakate所暗示的，使用段树(我在实现中使用了Fenwick树)的解决方案在O(n log M)时间内运行，其中M是数组中可能的最大值。假设M是常数(嘿，它被int的大小所限制)，那么算法在O(n)中运行。对不起，如果你觉得我在报告复杂性时作弊，但是，从技术上讲，这是真的!= D

Firstly, note that the problem "number of smaller elements on the left" is equivalent to the problem "number of greater elements on the right" by reversing and negating the array. So, in my explanation below I only describe the "number of smaller elements on the left", which I call "lesser_left_count".

首先要注意的是，问题“左边的小元素数”等同于问题“右边的大元素数”，这是通过对数组进行反转和否定来实现的。所以，在下面的解释中，我只描述了“左边的小元素的数量”，我称之为“lesser_left_count”。

Algorithm for lesser_left_count:

lesser_left_count算法:

The idea is to be able to find the total of numbers smaller than a specific number.

这样做的目的是找到比特定数字小的总数。

1. Define an array tree with size upto MAX_VALUE, which will store the value 1 for seen numbers and 0 otherwise.

   定义一个数组树，其大小为MAX_VALUE，它将为已看到的数字存储值1，否则存储值0。

2. Then as we traverse the array, when we see a number num, just assign the value 1 to tree[num] (update operation). Then lesser_left_count for a number num is the sum from 1 to num-1 (sum operation) so far, since all smaller numbers to the left of current position would have been set to 1.

   然后当我们遍历数组时，当我们看到数字num时，只需将值1赋给树[num](更新操作)。然后，一个数字num的lesser_left_count是到目前为止从1到num1 (sum操作)的总和，因为当前位置左边的所有小数字都将被设置为1。

Simple right? If we use Fenwick tree, the update and sum operation can be done each in O(log M) time, where M is the maximum possible value in the array. Since we are iterating over the array, total time is O(n log M), or simply O(n) if we regard M as a constant (in my code I set it to 2^20-1 = 1048575, so it's O(20n), which is O(n))

简单的对吧?如果我们使用Fenwick树，更新和求和操作可以在O(log M)时间内完成，其中M是数组中可能的最大值。由于我们遍历该数组,总时间是O(n日志M),或者仅仅是O(n),如果我们认为M是一个常数(我在代码设置为2 ^ 20—1 = 1048575,这是O(n)20日,这是O(n))

The only disadvantage of the naive solution is that it uses a lot of memory as M gets bigger (I set M=2^20-1 in my code, which take around 4MB of memory). This can be improved by mapping distinct integers in the array into smaller integers (in a way that preserve the order). The mapping can be done in simply O(n log n) by sorting the array (ok, that makes the complexity O(n log n), but as we know that n < M, you can regard that as O(n)). So the number M can be reinterpreted as "number of distinct elements in the array".

天真的解决方案的唯一的缺点是,它使用很多内存M变大(我设置M = 2 ^为20:1在我的代码中,以约4 mb的内存)。通过将数组中的不同整数映射为更小的整数(以保持顺序的方式)，可以改进这一点。映射可以通过排序数组(好吧，这使得复杂度为O(n log n)来完成，但是我们知道n < M，你可以把它看成O(n))因此，数字M可以被重新解释为“数组中不同元素的数量”。

So the memory wouldn't be any problem anymore, because if after this improvement you indeed need huge memory, that means there are that many distinct numbers in your array, and the time complexity of O(n) will already be too high to be calculated in normal machine anyway.

内存不会再有问题了，因为如果改进后你确实需要很大的内存，这就意味着你的数组中有很多不同的数字，O(n)的时间复杂度已经太高了，在正常的机器上是无法计算的。

For the sake of simplicity, I didn't include that improvement in my code.

为了简单起见，我没有在代码中包含这个改进。

Oh, and since Fenwick tree only works for positive numbers, I converted the numbers in the array to be minimum 1. Note that this doesn't change the result.

因为芬威克树只适用于正数，所以我将数组中的数转换为最小的1。注意，这不会改变结果。

Python code:

Python代码:

MAX_VALUE = 2**20-1
f_arr = [0]*MAX_VALUE

def reset():
    global f_arr, MAX_VALUE
    f_arr[:] = [0]*MAX_VALUE

def update(idx,val):
    global f_arr
    while idx<MAX_VALUE:
        f_arr[idx]+=val
        idx += (idx & -idx)

def cnt_sum(idx):
    global f_arr
    result = 0
    while idx > 0:
        result += f_arr[idx]
        idx -= (idx & -idx)
    return result

def count_left_less(arr):
    reset()
    result = [0]*len(arr)
    for idx,num in enumerate(arr):
        cnt_prev = cnt_sum(num-1)
        if cnt_sum(num) == cnt_prev: # If we haven't seen num before
            update(num,1)
        result[idx] = cnt_prev
    return result

def count_left_right(arr):
    arr = [x for x in arr]
    min_num = min(arr)
    if min_num<=0:                       # Got nonpositive numbers!
        arr = [min_num+1+x for x in arr] # Convert to minimum 1
    left = count_left_less(arr)
    arr.reverse()                        # Reverse for greater_right_count
    max_num = max(arr)
    arr = [max_num+1-x for x in arr]     # Negate the entries, keep minimum 1
    right = count_left_less(arr)
    right.reverse()                      # Reverse the result, to align with original array
    return (left, right)

def main():
    arr = [1,1,3,2,4,5,6]
    (left, right) = count_left_right(arr)
    print 'Array: ' + str(arr)
    print 'Lesser left count: ' + str(left)
    print 'Greater right cnt: ' + str(right)

if __name__=='__main__':
    main()

will produce:

会产生:

Original array:    [1, 1, 3, 2, 4, 5, 6]
Lesser left count: [0, 0, 1, 1, 3, 4, 5]
Greater right cnt: [5, 5, 3, 3, 2, 1, 0]

or if you want Java code:

或者如果你想要Java代码:

import java.util.Arrays;

class Main{
    static int MAX_VALUE = 1048575;
    static int[] fArr = new int[MAX_VALUE];

    public static void main(String[] args){
        int[] arr = new int[]{1,1,3,2,4,5,6};
        System.out.println("Original array:    "+toString(arr));
        int[][] leftRight = lesserLeftRight(arr);
        System.out.println("Lesser left count: "+toString(leftRight[0]));
        System.out.println("Greater right cnt: "+toString(leftRight[1]));
    }

    public static String toString(int[] arr){
        String result = "[";
        for(int num: arr){
            if(result.length()!=1){
                result+=", ";
            }
            result+=num;
        }
        result+="]";
        return result;
    }

    public static void reset(){
        Arrays.fill(fArr,0);
    }

    public static void update(int idx, int val){
        while(idx < MAX_VALUE){
            fArr[idx]+=val;
            idx += (idx & -idx);
        }
    }

    public static int cntSum(int idx){
        int result = 0;
        while(idx > 0){
            result += fArr[idx];
            idx -= (idx & -idx);
        }
        return result;
    }

    public static int[] lesserLeftCount(int[] arr){
        reset();
        int[] result = new int[arr.length];
        for(int i=0; i<arr.length; i++){
            result[i] = cntSum(arr[i]-1);
            if(cntSum(arr[i])==result[i]) update(arr[i],1);
        }
        return result;
    }

    public static int[][] lesserLeftRight(int[] arr){
        int[] left = new int[arr.length];
        int min = Integer.MAX_VALUE;
        for(int i=0; i<arr.length; i++){
            left[i] = arr[i];
            if(min>arr[i]) min=arr[i];
        }
        for(int i=0; i<arr.length; i++) left[i]+=min+1;
        left = lesserLeftCount(left);

        int[] right = new int[arr.length];
        int max = Integer.MIN_VALUE;
        for(int i=0; i<arr.length; i++){
            right[i] = arr[arr.length-1-i];
            if(max<right[i]) max=right[i];
        }
        for(int i=0; i<arr.length; i++) right[i] = max+1-right[i];
        right = lesserLeftCount(right);
        int[] rightFinal = new int[right.length];
        for(int i=0; i<right.length; i++) rightFinal[i] = right[right.length-1-i];
        return new int[][]{left, rightFinal};
    }
}

which will produce same result.

这将产生同样的结果。

#2

Try segment tree data structure used for solving RMQ. It would give you exactly n log n.

尝试使用分段树数据结构来解决RMQ。结果是n log n。

And look through RMQ problem generally, your problem may be reduced to it.

一般地看一下RMQ问题，你的问题可以归结为它。

#3

Here's a relatively simple solution that's O(N lg(N)) that doesn't rely on the entries being among finitely many integers (in particular, it should work for any ordered data type).

这里有一个相对简单的解决方案，即O(nlg (N))，它不依赖于有限多个整数中的条目(特别是，它应该适用于任何有序数据类型)。

We assume the output is to be stored in two arrays; lowleft[i] will at the end contain the number of distinct values x[j] with j < i and x[j] < x[i], and highright[i] will at the end contain the number of distinct values x[j] with j > i and x[j] > x[i].

假设输出存储在两个数组中;lowleft[i]最后将包含不同值x[j]和j < i和x[j] < x[i]的个数，highright[i]最后将包含不同值x[j]和j > i和x[j] > [i]的个数。

Create a balanced tree data structure that maintains in each node, the number of nodes in the subtree rooted at that node. This is fairly standard, but not a part of the Java standard library I think; it's probably easiest to do an AVL tree or so. The type of the values in the nodes should be the type of the values in your array.

创建一个均衡的树数据结构，在每个节点中维护子树中位于该节点的节点数。这是相当标准的，但不是我认为的Java标准库的一部分;这可能是最容易做的AVL树。节点中的值的类型应该是数组中的值的类型。

Now first iterate forward through the array. We start with an empty balanced tree. For every value x[i] we encounter, we enter it into the balanced tree (near the end there are O(N) entries in this tree, so this step takes O(lg(N)) time). When searching for the position to enter x[i], we keep track of the number of values less than x[i] by adding up the sizes of all left subtrees whenever we take the right subtree, and adding what will be the size of the left subtree of x[i]. We enter this number into lowleft[i].

现在首先遍历数组。我们从一个空的平衡树开始。对于我们遇到的每一个值x[i]，我们将它输入到平衡树中(在树的末端有O(N)个元素，所以这个步骤需要O(lg(N)时间)。在搜索输入x[i]的位置时，我们跟踪小于x[i]的值的数量，每当我们取右子树时，我们将所有左子树的大小相加，然后再加上x[i]左子树的大小。我们在左下角输入这个数字[i]。

If the value x[i] is already in the tree, we just carry on with the next iteration of this loop. If the value x[i] is not in there, we enter it and rebalance the tree, taking care to update the subtree sizes correctly.

如果值x[i]已经在树中，我们就继续进行这个循环的下一个迭代。如果值x[i]不在其中，我们输入它并重新平衡树，注意正确更新子树大小。

Each iteration of this loop takes O(lg(N)) steps, for a total of O(N lg(N)). We now start with an empty tree and do the same thing iterating backward through the array, finding the position for every x[i] in the tree, and every time recording the size of all subtrees to the right of the new node as highright[i]. Total complexity therefore O(N lg(N)).

这个循环的每次迭代都有O(lg(N)步，总共有O(N lg(N))步。现在我们从一个空树开始，做同样的事情，遍历数组，找到树中每一个x[i]的位置，每次将新节点右边的所有子树的大小记录为highright[i]。总复杂度O(nlgn)

#4

Here is an algorithm which should give you O(NlgN):

这里有一个算法，它应该给你O(NlgN):

1. Iterate over the list once and build a map of key => indexList. So for ever key (element in the array) you store a list of all the indices where that key is in the array. This will take O(N) (iterate over the list) + N*O(1) (appending N items to lists) steps. So this step is O(N). The second step requires that these lists are sorted which they will be as we are iterating over the list from left to right so a newly inserted index in a list will always be larger than all the other ones which are already in there.

   遍历列表一次，构建key =>索引列表的映射。因此，对于任何键(数组中的元素)，都要存储数组中键所在的所有索引的列表。这将采取O(N)(遍历列表)+ N*O(1)(向列表添加N项)步骤。这一步是O(N)第二步需要对这些列表进行排序，当我们从左到右对列表进行迭代时，这些列表将被排序，因此，列表中新插入的索引将始终大于列表中已经存在的所有其他索引。

2. Iterate over the list again and for each element search the index lists for all keys which are larger than the current element for the first index which is after the current index. This gives you the number of elements to the right of the current one which are larger than the current element. As the index lists are sorted you can do a binary search which will take O(k * lgN) steps with k being the number of keys larger then the current one. If the number of keys has an upper limit then this is a constant as far as big-O is concerned. The second step here is to search all smaller keys and find the first index in the list which is prior to the current one. This will give you the number of element to the left of the current one which are smaller. Same reasoning as above this is O(k * lgN)

   再次遍历列表，对每个元素搜索索引列表，查找在当前索引之后的第一个索引中大于当前元素的所有键。这将给出当前元素右边的元素数量，这些元素的数量大于当前元素。当索引列表被排序时，你可以做一个二进制搜索，它将采取O(k * lgN)步骤，k是比当前的那个更大的键的数量。如果键的数量有上限，那么对于大o来说，这是一个常数。这里的第二步是搜索所有较小的键并找到列表中的第一个索引，该索引在当前索引之前。这将给出当前元素左边的元素的数量，而这个元素比较小。与上面相同的推理是O(k * lgN)

So assuming the number of keys is limited this should give you O(N) + N * 2 * O(lgN) so overall O(NlgN) if I'm not mistaken.

假设键的数量是有限的这应该给你O(N) + N * 2 * O(lgN)所以总的来说O(NlgN)如果我没弄错的话。

Edit: Pseudo code:

编辑:伪代码:

int[] list;
map<int => int[]> valueIndexMap;
foreach (int i = 0; i < list.length; ++i) {       // N iterations
   int currentElement = list[i];                     // O(1)
   int[] indexList = valueIndexMap[currentElement];  // O(1)
   indexList.Append(i);                              // O(1)
}

foreach (int i = 0; i < list.length; ++i) {  // N iterations
    int currentElement = list[i];            // O(1)
    int numElementsLargerToTheRight;
    int numElementsSmallerToTheLeft;
    foreach (int k = currentElement + 1; k < maxKeys; ++k) {  // k iterations with k being const
       int[] indexList = valueIndexMap[k];                                            // O(1)
       int firstIndexBiggerThanCurrent = indexList.BinaryFindFirstEntryLargerThan(i); // O(lgN)
       numElementsLargerToTheRight += indexList.Length - firstIndexBiggerThanCurrent;  // O(1)
    }
    foreach (int k = currentElement - 1; k >= 0; --k) {  // k iterations with k being const
       int[] indexList = valueIndexMap[k];                                            // O(1)
       int lastIndexSmallerThanCurrent = indexList.BinaryFindLastEntrySmallerThan(i); // O(lgN)
       numElementsSmallerToTheLeft += lastIndexSmallerThanCurrent;                    // O(1)
    }
}

Update: I tinkered around with a C# implementation in case anyone is interested;

更新:我修改了c#实现，以防有人感兴趣;