2011-05-22 50 views
6

我遇到了問題,並提供了一個OK-ish解決方案。我希望有更好的解決方案。尋找任意子陣列中所有項目總和的最佳算法

問題

我有大約20萬整數數組。給定兩個指數i1和i2,我需要計算i1和i2之間所有元素的總和。數組中的每個整數都在1到4之間。例如:

a = [1, 3, 2, 4, 3, 2, 4, 1]; 
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2) 

此操作將執行大約200,000次,因此需要非常快。 for循環中的簡單計數器是O(n),而且太慢了。陣列在施工後從不修改,所以可以有相對昂貴的預處理階段。

我最好的解決方案至今

這種算法工作在O(log n)的時間:

第一焊盤原始數組用零,直到其長度爲二的冪。接下來,將數組分成兩個相等的部分並存儲每個的總和。然後將數組分成四個部分並存儲每個部分的總和。然後八分之一。繼續這樣做直到數組被分成2個元素長的段。對於上面的8個元素的陣列,這需要兩個步驟:

halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])] 
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])] 

然後給出兩個指數,現在有可能制定出subsection_sum在O(log n)的時間。例如,subsection_sum(a,2,7)== quarters [1] + halfves [1]。

回答

14

介紹一個包含累計和的輔助數組。也就是說,輔助陣列的元素i具有原始陣列的元素0到i的總和。子陣列總和就是輔助陣列中兩個元素的差異。這會在一段時間內給出結果,O(1)

這取決於在這個問題給出的subsection_sum功能不變,:

subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2) 

在那裏我假設i1 <= i2。重新整理,我們有:

subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1) 

注意,在右側的款項均來自0開始。輔助數組可以被視爲緩存總和值爲零,subsection_sum(a, 0, i),全部爲i

+0

完美,我不敢相信我想到了這樣一個複雜的解決方案,錯過了一個簡單的解決方案!謝謝。 – 2011-05-22 14:36:39

+1

與我的解決方案一樣,但是卻擊敗了我! +1 – 2011-05-22 14:38:08

3

如果可以承受O(n)額外的存儲,則可以創建一個查找表,其i個要素是所述元件中的索引0通過i(含)的輸入陣列中的總和。在僞代碼:

def computeLookupTable(arr): 
    let n = arr.length 
    let lookupTable = new Array() 

    lookupTable[0] = arr[0] 

    for i=1 to n: 
     lookupTable[i] = arr[i] + lookupTable[i-1] 

    return lookupTable 

然後你就可以使用此表通過採取差別

lookupTable[i2] - lookupTable[i1] 

這需要一定的時間來計算i1i2之間array所有元素的總和。

+2

我想說,我們提出了很好的補充說明。 – 2011-05-22 14:40:03

相關問題