3

我有以下需要优化的问题。对于给定的数组（允许重复键），对于i数组中的每个位置，我需要计算 右侧的所有较大值i和左侧的所有较小值i。如果我们有：

1 1 4 3 5 6 7和i = 3（值 3），左侧的较小值的数量i是1（没有重复的键），右侧，较大的值的数量是3。

这个问题的蛮力解决方案是~N^2，并且有了一些额外的空间，我可以设法从较大的值中计算出较小的值，从而将复杂性降低到~(N^2)/2. 我的问题是：有没有更快的方法来完成它？也许NlgN？我想那里有一个我不知道的数据结构可以让我更快地进行计算。

编辑：谢谢大家的回复和讨论。您可以找到两个很好的解决方案两个以下问题。在 stackoverflow 中向开发人员学习总是一种乐趣。

4

4 回答 4

3

这是一个O(n log n)解决方案。

正如@SayonjiNakate 所暗示的，使用段树的解决方案（我在我的实现中使用了 Fenwick 树）O(n log M)及时运行，其中M是数组中的最大可能值。

首先，注意问题“左边的较小元素的数量”等价于问题“右边的较大元素的数量”，通过反转和取反数组。因此，在我下面的解释中，我只描述了“左侧较小元素的数量”，我称之为“lesser_left_count”。

lesser_left_count 的算法：

这个想法是能够找到小于特定数字的数字总数。

  1. tree定义一个大小为 upto的数组MAX_VALUE，它将存储1所见数字的值以及0其他值。

  2. 然后当我们遍历数组时，当我们看到一个数字时num，只需将值分配1给tree[num]（更新操作）。然后，一个数字的 lesser_left_countnum是从1到num-1( sum operation ) 的总和，因为当前位置左侧的所有较小数字都将被设置为1。

简单吧？如果我们使用Fenwick tree，更新和求和操作可以每次都O(log M)及时完成，其中M是数组中的最大可能值。由于我们正在遍历数组，因此总时间为O(n log M).

天真的解决方案的唯一缺点是它使用的内存M越来越大（我M=2^20-1在我的代码中设置了大约 4MB 的内存）。这可以通过将数组中的不同整数映射为更小的整数来改进（以保持顺序的方式）。映射可以简单地O(n log n)通过对数组进行排序来完成。所以这个数字M可以重新解释为“数组中不同元素的数量”。

所以内存不再是任何问题，因为如果经过这个改进之后你确实需要巨大的内存，那意味着你的数组中有很多O(n)不同的数字，时间复杂度已经太高了，无法在普通机器上计算反正。

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

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

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()

将产生：

原始数组：[1, 1, 3, 2, 4, 5, 6]
左数较少：[0, 0, 1, 1, 3, 4, 5]
大右 cnt：[5, 5, 3, 3, 2, 1, 0]

或者如果你想要 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};
    }
}

这将产生相同的结果。

于 2013-09-25T07:12:35.730 回答
2

尝试用于解决 RMQ 的分段树数据结构。它会给你准确的 n log n。

而且一般看RMQ问题，你的问题可能会归结为它。

于 2013-09-24T23:16:09.630 回答
2

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

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

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

现在首先遍历数组。我们从一棵空的平衡树开始。对于我们遇到的每个值x[i]，我们将其输入到平衡树中（接近末尾的树中有O(N)条目，因此这一步需要O(lg(N))时间）。在搜索要输入的位置时x[i]，我们通过将所有左子树的大小相加来跟踪值的数量，x[i]只要我们取右子树，然后添加左子树的大小x[i]。我们将这个数字输入到lowleft[i].

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

此循环的每次迭代都采取O(lg(N))步骤，总共O(N lg(N)). 我们现在从一棵空树开始，并在数组中向后x[i]迭代做同样的事情，找到树中每个的位置，并且每次都将新节点右侧的所有子树的大小记录为highright[i]。因此，总复杂性O(N lg(N))。

于 2013-09-25T19:24:01.560 回答
0

这是一个应该给你的算法O(NlgN)：

  1. 遍历列表一次并构建key => indexList. 因此，对于任何键（数组中的元素），您都存储了该键在数组中的所有索引的列表。这将采取O(N)（迭代列表）+ N*O(1)（将 N 个项目附加到列表）步骤。所以这一步是O(N)。第二步需要对这些列表进行排序，因为我们从左到右遍历列表，因此列表中新插入的索引将始终大于所有其他已在列表中的索引。

  2. 再次遍历列表，并为每个元素在索引列表中搜索大于当前元素的所有键，以查找当前索引之后的第一个索引。这为您提供了当前元素右侧大于当前元素的元素数量。随着索引列表的排序，您可以进行二进制搜索，该搜索将采取O(k * lgN)步骤k使键的数量大于当前的数量。如果键的数量有上限，那么就 big-O 而言，这是一个常数。这里的第二步是搜索所有较小的键，并在列表中找到当前索引之前的第一个索引。这将为您提供当前元素左侧较小的元素数量。与上述相同的推理是O(k * lgN)

所以假设键的数量是有限的，如果我没记错的话，这应该会给你一个O(N) + N * 2 * O(lgN)整体。O(NlgN)

编辑：伪代码：

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)
    }
}

更新：我修改了一个 C# 实现，以防有人感兴趣；

于 2013-09-25T01:12:51.950 回答