如何優化代碼當前算法取O（n + m + k）？

Question

我有三個陣列，h1, h2, h3。

n1, n2,n3決定陣列的長度。

我必須從1個或多個數組中刪除輸入，以便所有數組的最終總和應該相同。

###Inputs 
n1,n2, n3 = 5, 3, 4 
h1 = 3 2 1 1 1 # 5 elements 
h2 = 4 3 2  # 3 elements 
h3 = 1 1 4 1 # 4 elements 

如果上述陣列

sum of h1 = 8 sum of h2 = 9 sum of h3 = 7 從數組開頭的deletion should happen中看到的。 所以在這裏，如果我刪除， 3 from h1 (as h1[0]) 4 from h2 (as h2[0]) 1 and 1 from h3 (as h3[0] and h3[1]) 現在所有(Sum of h1 containts, h2 containts, h3 containts)總和將成爲5。這是我的最終答案。 當輸入列表很小時，下面的代碼表現很好。但是當輸入列表變爲n1 = 100000, n2 = 200000, n3 = 300000。這段代碼需要很多時間來執行。我怎樣才能縮短時間。

from collections import * 
n1,n2,n3 = input().strip().split(' ') 
n1,n2,n3 = [int(n1),int(n2),int(n3)] 
h1 = [int(h1_temp) for h1_temp in input().strip().split(' ')] 
h2 = [int(h2_temp) for h2_temp in input().strip().split(' ')] 
h3 = [int(h3_temp) for h3_temp in input().strip().split(' ')] 
#print(n1, n2, n3, h1, h2, h3) 
h1_tot, h2_tot, h3_tot = sum(h1), sum(h2), sum(h3) 
#print(h1_tot, h2_tot, h3_tot) 
arr = [h1_tot, h2_tot, h3_tot] 
done = False 
while len(Counter(arr)) != 1: 
    if len(Counter(arr)) == 3: 
     if arr.index(min(Counter(arr))) == 0: 
      h3.remove(h3[0]) 
      h2.remove(h2[0]) 
     elif arr.index(min(Counter(arr))) == 1: 
      h3.remove(h3[0]) 
      h1.remove(h1[0]) 
     else: 
      h1.remove(h1[0]) 
      h2.remove(h2[0]) 
    if len(Counter(arr)) == 2: 
     index = arr.index(min(arr)) 
     if arr[0] == arr[1] and index == 2: 
      h1.remove(h1[0]) 
      h2.remove(h2[0]) 
     elif arr[1] == arr[2] and index == 0: 
      h2.remove(h2[0]) 
      h3.remove(h3[0]) 
     elif arr[0] == arr[2] and index == 1: 
      h1.remove(h1[0]) 
      h3.remove(h3[0]) 
     if arr[0] == arr[1] and (index == 0 or index == 1): 
      h3.remove(h3[0]) 
     elif arr[1] == arr[2] and (index == 2 or index == 1): 
      h1.remove(h1[0]) 
     elif arr[0] == arr[2] and (index == 0 or index == 2): 
      h2.remove(h2[0]) 

    h1_tot, h2_tot, h3_tot = sum(h1), sum(h2), sum(h3) 

    arr = [h1_tot, h2_tot, h3_tot] 



print(arr[0]) 

Answer 1

從Python列表的開始刪除慢（O(N)），因爲Python需要引用複製到所有其他項目到一個新的指數（移動起來一個空格）。相反，從列表末尾刪除的速度很快（O(1)），因爲它只刪除一個引用並調整大小。

因此，爲了提高算法的性能，我建議使用反轉列表，以便首先刪除的項目在最後。您可以使用列表理解中的reversed函數或在列表創建後使用list.reverse方法將它們反轉。一旦你完成了你的算法，你可以通過反轉再次把它們放回預期的順序。

您還需要使用list.pop或del some_list[-1]而非list.remove，因爲後者仍然會在年底慢（因爲它需要在列表中搜索項刪除）。

儘管我不認爲它會傷害你的表現，但你也有很多非常重複的代碼。當你看到這些變量並且它們中包含數字的變量時，通過使用可索引數據結構而不是獨立變量，幾乎總是表明可以簡化代碼。以下是我如何使用列表清單（以及它們的總和清單，以便衡量）解決您的問題：

lengths = [int(x) for x in input().split()] # this is ignored by the rest of the code 

values = [[int(x) for x in reversed(input().split())] for _ in range(3)] # make a list of 
sums = [sum(v) for v in values]           # reversed lists 

while not sums[0] == sums[1] == sums[2]: # if there wasn't a fixed number of lists, I'd use 
    max_sum = max(sums)     # something like "if max(sums) == min(sums)" 
    for i, (v, s) in enumerate(zip(values, sums)): # this loop over the lists lets us avoid 
     if s == max_sum:       # duplicating our code for each one 
      sums[i] -= v.pop(-1) # pop is fast at the end! 

for v in values: # I'm not sure what the desired output is, so I'm just printing the lists. 
    v.reverse() # Could instead use print(*reversed(v)) for formatting like in the input. 
    print(v)