爲陣列位置計算越來越大的值

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