java - 计算数组位置的更小和更大的值

Question

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

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

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

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

Answer 1

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

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

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

lesser_left_count 的

算法:

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

1. 定义一个大小为 tree 的数组 MAX_VALUE，它将为已见数字存储值 1，否则为 0。

2. 然后当我们遍历数组时，当我们看到数字 num 时，只需将值 1 赋给 tree[num](更新操作)。那么数字 num 的 lesser_left_count 是到目前为止从 1 到 num-1 的总和(求和运算)，因为当前位置左侧的所有较小数字都将设置为 1。

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

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

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

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

哦，因为芬威克树只适用于正数，所以我将数组中的数字转换为最小值 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()

将产生:

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:

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

这将产生相同的结果。