在給定陣列中的範圍L的值查找至R

鑑於陣列甲，和兩個索引大號和ř，找到的在給定陣列中的範圍L的值查找至R

Summation(AS[i]*AS[j]*AS[k])

其中L<=i<j<k<=R值並且AS是排序集的所有元素A的範圍爲L到01包括。

例：讓A=(4,4,1,6,1,3)L=0和R=3給AS=(1,4,6)，所以Ans=1*4*6=24

我沒有任何辦法比爲O（n^3），這是非常緩慢的。請給我建議一些更快的方法。 A中的元素數量高達10^5。

來源

2015-08-15 Rishabh

是否有任何約束的子集？ – Paul

L和R可以是任意值。有一件事肯定L <= R。 – Rishabh

這很清楚，但問題是這個子集有任何限制。到目前爲止，你所要做的就是對數組進行排序，並採用索引爲 L的任意三個值，這可以通過排序算法的時間複雜性來解決 – Paul

正如問題評論員所說，確定AS可以通過使用散列表H完成。您只需遍歷從L索引A到R的元素，並將每個元素插入到H。結果應該是你需要的一組元素。你仍然需要對這個集合進行排序。爲此，您可以將H的元素複製到數組中並對該數組進行排序。結果是AS。這應該不會超過O(NlogN)步驟，其中N=R-L。

評論員沒有說的是如何有效地計算總和。它可以在O(N)步驟完成。這是如何。

我們首先進行如下觀察：

Sum(AS[j]*AS[k], a <= j < k <= b) = 
    1/2*(AS[a] + AS[a+1] + ... + AS[b])^2 - 
    1/2*(AS[a]^2 + AS[a+1]^2 + ... + AS[b]^2)

我們擴大我們的目標總如下：

S = Sum(AS[i]*AS[j]*AS[k]) = 
    AS[L] * Sum(AS[j]*AS[k], L+1 <= j < k <= R) +  (iteration  1) 
    AS[L+1] * Sum(AS[j]*AS[k], L+2 <= j < k <= R) +  (iteration  2) 
    ... 
    AS[R-2] * Sum(AS[j]*AS[k], R-1 <= j < k <= R).  (iteration R-L-1)

我們現在應用的觀察。

爲了確定形式Sum(AS[j]*AS[k], a <= j < k <= b)的總和有效地我們可以首先計算

S1 = AS[L] + AS[L+1] + ... + A[R] 
S2 = AS[L]^2 + AS[L+1]^2 + ... + A[R]^2

然後遞增來自每個總和中減去第一項，因爲我們通過的AS元素迭代從索引L到R-2。

因此，在確定AS之後，確定所需的總和可以在O(N)步驟完成。如果您使用某種比較排序方法，則整個算法應執行O(|A|) + O(NlogN) + O(N)步驟。

來源

2015-08-16 02:01:34 cobarzan

在給定陣列中的範圍L的值查找至R

回答

相關問題