为阵列位置计算越来越大的值

Question

我有以下需要优化的问题。对于给定的数组（允许有重复的键），对于阵列中的每个位置i，我需要计算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)，我在这里给你一个技术上的O(n)解决方案。

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

首先，请注意，通过反转和取反数组，问题“左侧的较小元素的数量”等同于“右侧的较大元素的数量”问题。所以，在我的下面的解释中，我只描述了“左侧较小元素的数量”，我称其为“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)，或者干脆O(n)如果我们把M为常数（在我的代码，我将它设置为2^20-1 = 1048575，所以它的O(20n)，这是O(n)）

的唯一的缺点天真的解决方案是，它使用了大量的内存，因为M变得更大（我在我的代码中设置了M=2^20-1，这占用了大约4MB的内存）。这可以通过将数组中的不同整数映射为更小的整数（以保持顺序的方式）来改进。通过对数组进行排序，可以简单地在O(n log n)中完成映射（好吧，这使得复杂度为O(n log n)，但是因为我们知道n < M，您可以将其视为O(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() 

会产生：

 
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] 

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

这将产生相同的结果。

Answer 2

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

一般来看通过RMQ problem，你的问题可能会减少到它。

Answer 3

这是一种算法，应该给你O(NlgN)：

1. 遍历目录一次，在地图上标注的key => indexList。因此，对于任何键（数组中的元素），您都存储该键在数组中的所有索引的列表。这将花费O(N)（遍历列表）+ N*O(1)（追加N个项目到列表）的步骤。所以这一步是O(N)。第二步需要对这些列表进行排序，因为我们从左向右迭代列表，所以列表中新插入的索引总是比其中已有的其他列表更大。

2. 重复遍历整个列表，并且对于每个元素，搜索所有大于当前索引之后的第一个索引的当前元素的键的索引列表。这会为当前元素右侧的元素数量提供大于当前元素的元素数量。由于索引列表已排序，因此您可以执行二分法搜索，该步骤将采用O(k * lgN)步骤，其中k是大于当前键的键数。如果键的数量有一个上限，那么就大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) 
    } 
} 

更新：我修修补补周围with a C# implementation如果有人有兴趣;

Answer 4

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

我们假设输出存储在两个数组中; lowleft[i]将在最后包含不同值的数量x[j]与j < i和x[j] < x[i]和highright[i]将在最后包含不同值的数量x[j]与j > i和x[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))。