組合增加爲零

給定五個分類列表：List1，List2，List3，List4，List5，每個長度爲n。如果有5個（整數）數字（每個列表中有1個），總計爲零返回true。我的目標是確保算法是O（n）。除了我的頭頂，我可以考慮創建一個哈希映射，其中包含5個鏈接列表的總和或評估5個列表，使得[o（n * n * n * n * n）]。我正在尋找優化或降低複雜性的方法，並且我被卡住了。組合增加爲零

我在Python代碼：

def getIndicesFromFiveArrays(List1,List2,List3,List4,List5,t): 
    a,b,c,d,e=0,0,0,0,0 
    while(List1[a]+List2[b]+List3[c]+List4[d]+List5[e]!=t): 
     b=b+1 
     if b==len(List2): 
      return (-1,-1) 
     if List1[a]+List2[b]+List3[c]+List4[d]+List5[e]<t: 
      a=a+1 
      b=b-1 
     c=c-1 
     d=d-1 
     e=e-1 
      if a==len(List1): 
       return (-1,-1) 
    return (a,b,c,d,e)

編輯1：這是不是對了功課，你可以檢查我的其他問題，並驗證自己。謝謝..

來源

2012-07-19 bouncingHippo

它不是作業.. – bouncingHippo 2012-07-19 14:24:55

這些列表是持有浮動還是隻是整數？ – NominSim 2012-07-19 14:32:24

這些列表包含整數 – bouncingHippo 2012-07-19 14:33:26

如果有2個列表，你將從列表1中取一個數字，然後在列表2中查找該數字的負數。如果用列表替換列表2，則總體複雜度爲O（ N）。

如果有3個列表，您將從列表1中獲取一個數字，然後從列表2中獲取一個，複雜度爲O（n^2）。如果用列表替換列表3，則總體複雜度爲O（n^2）。

所以我認爲5個列表/集合的整體複雜度不能降到O（n^4）以下。

來源

2012-07-19 14:57:14 MRAB

這些清單是排序的，它允許在一般情況下不可能的O（n）解決方案，至少對於2個清單是可能的。我不確定如何推廣它。 – 2012-07-19 15:01:52

O（n^4）？它可以減少。 – 2012-07-19 21:55:20

肯定可以減少到O（n^4）以下。 – xvatar 2012-07-19 22:46:06

有一個O（n^3）解決方案，受MRAB評論的啓發。

首先，將列表1中的每個值與列表2中的每個值組合並將其存儲在一個集合中。調用結果集1和2，它有n^2個值。

接下來，將set 1and2與list 3相結合。調用結果集1and2and3，它有n^3個值，並且需要n^3個步驟來構造。

接下來，結合列表4和5.調用結果集4和5，它有n^2個值。

最後，檢查集合4和5中的任何值是否等於集合1和2和3中值的倒數。這一步需要n^2個步驟。

該方法使用O（n^3）空間和O（n^3）時間。

正如Karoly Horvath指出的那樣，您實際上並不需要存儲set 1and2and3，您可以在最後一步中從set 1and2中快速構建它。此方法僅使用O（n^2）空間，但仍需要O（n^3）時間。這裏是代碼：

l1 = [1,2,3,4,5,10] 
l2 = [1,2,3,4,5,11] 
l3 = [1,2,3,4,5,12] 
l4 = [1,2,3,4,5,13] 
l5 = [1,2,3,4,5,-46] 

def test(): 
    l1_2 = [a + b for a in l1 for b in l2] 
    set4_5 = set([a + b for a in l4 for b in l5]) 
    return any([True for x in l1_2 for y in l3 if -(x + y) in set4_5]) 

print test()

來源

2012-07-19 21:21:16 RossFabricant

你可以用O（n^2）空間來做到這一點，它足以存儲1and2。 – 2012-07-19 21:57:40

@Kolyoly Horvath：我可以看到在O（n^3）中如何做到這一點，但不是O（n^2）。 – MRAB 2012-07-19 23:40:57

組合增加爲零

回答

相關問題