什麼是用於此問題的最佳算法

序列的均衡索引是一個索引，使得較低索引處元素的總和等於較高索引處元素的總和。例如，在一個序列A：什麼是用於此問題的最佳算法

A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0

3是一種平衡指數，這是因爲：

A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

6也是平衡指數，這是因爲：

A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0

（零總和元素爲零）7不是平衡指數，因爲它不是序列A的有效索引。如果仍有疑問，這是一個精確定義：整數k是序列的均衡索引if並且只有在和。

假設零元素的總和等於零。寫的函數

int equi(int[] A);

該給定的序列，返回其平衡指數（任何），或者如果沒有平衡索引存在-1。假設序列可能很長。

來源

2011-01-05 slim

對於那些試圖讀取此，該序列我s'{-7,1,5,2 -4,3,0}' – 2011-01-05 23:22:53

計算所有的元素的在A
總和對於每個索引i，計算從A[0]的元素的總和A[i - 1]，直到總和等於(totalSum - A[i])/2。

注意，從A[0]元件以A[i - 1]總和可被跟蹤爲運行總計，這意味着整個算法的複雜度是O（n）。作爲代碼實現是作爲讀者的練習。

來源

2011-01-05 22:46:12

這可能會在任意序列上失敗，因爲均衡指數並不總是涉及該系列的所有元素。在{1,2,3,4,5,10}系列中，根據給出的定義，4是平衡指數，但是元素0-3的總和是10，小於元素總和除以2.實際上，沒有任何元素的子集可以與該值相加，但是存在均衡指數。 – 2011-01-05 22:55:42

確實如此，如果我們發現我們的部分和大於總和的一半，則返回-1;' – EnabrenTane 2011-01-05 23:01:17

@哈珀，我沒有看到「均衡指數」的定義排除了價值在那個指數。我已經更新了我的答案。 – 2011-01-05 23:06:08

這是一個使用O(n)內存的解決方案。計算S[i] = A[0] + A[1] + ... + A[i]。那麼子序列[i, j]的總和是Sum(i, j) = S[j] - S[i - 1]（S[x < 0] = 0）。

因此，對於每個i從0到A.Length - 1檢查是否Sum(0, i - 1) = Sum(i + 1, A.Length - 1)。

事實上，如果你被允許銷燬給定的數組，你甚至不需要S，你可以在A中做到這一切。

來源

2011-01-05 23:03:53 IVlad

僞代碼 - 最壞的情況是2次通過A.

R = sum(A) 
L = e = 0 
for i = 0 .. A.size 
    L+=e 
    R-=(e=A[i]) 
    return i if L==R 
end 
return NULL

來源

2011-01-05 23:20:24 AShelly

A =（-7，1，5,2，-4，3，0）

sumleft = 0

sumright = 0
在範圍
對於i （LEN（A））：
for j in range(i+1,len(a)): 

    sumright += a[j] 

if sumright == sumleft: 

    print i 

sumleft += a[i] 

sumright = 0 

來源

2014-02-28 03:54:46 Jayr

什麼是用於此問題的最佳算法

回答

相關問題