該算法是否有O（N）解決方案？

-1

numbers = [1, 2, 4, 4, 4, 4, 5, 5, 5, 7, 7, 8, 8, 8, 9] 

match = [] 
for i in range(len(numbers)): 
    for j in range(len(numbers)): 
     if (i!=j): 
      if(numbers[i] + numbers[j] == sum): 
       match.append([numbers[i], numbers[j]])

我需要檢查的匹配以及重複，所以需要將輸出看起來像[[1, 9], [2, 8], [2, 8], [2, 8], [5, 5], [5, 5], [5, 5], [5, 5], [5, 5], [5, 5], [8, 2], [8, 2], [8, 2], [9, 1]]

來源

2017-06-16 joe

如果所有的數字都等於'總和/ 2'，會爲O （n^2）對，因此在一般情況下O（n）（或更一般地說比O（n^2）更快的任何事情）是不可能的（因爲沒有算法的時間複雜度比它產生的輸出大小更小）。 – Dukeling

你會很好地用文字描述算法應該做什麼。代碼告訴計算機要做什麼，只有你的評論可以告訴我們你想要做什麼。 – Richard

包括重複項和相反的有序對，加起來總和 – joe

這是一個變量：

from collections import Counter 


def sum_target(lst, target): 

    unique_list = list(set(lst)) 
    counts = Counter(lst) 

    remainders = {number: target-number for number in unique_list} 

    match = set() 
    for a, b in remainders.items(): 
     if b in remainders: 
      match.add(tuple(sorted((a, b)))) 

    # restore multiplicities: 
    ret = [] 
    for a, b in match: 
     if a != b: 
      mult = counts[a] * counts[b] 
      ret.extend([a, b] for _ in range(mult)) 
      ret.extend([b, a] for _ in range(mult)) 
      # ret.append((mult, (a, b))) 
      # ret.append((mult, (b, a))) 
     else: 
      mult = counts[a] * (counts[a]-1) 
      ret.extend([a, a] for _ in range(mult)) 
      # if mult != 0: 
       # ret.append((mult, (a, b))) 

    return ret

不能完全肯定的多重性的處理你所希望的方式（在你的榜樣，他們的兩倍那些我得到...爲什麼有6個版本的[5, 5]？有三個5只在你原來的列表中，您只拿到3對組...）

，如果你的列表中有很多重複再給予您的輸出我建議改變我的代碼的最後部分的長度

# restore multiplicities: 
ret = [] 
for a, b in match: 
    if a != b: 
     mult = counts[a] * counts[b] 
     ret.append((mult, (a, b))) 
     ret.append((mult, (b, a))) 
    else: 
     mult = counts[a] * (counts[a]-1) 
     if mult != 0: 
      ret.append((mult, (a, b)))

得到的結果

numbers = [1, 2, 4, 4, 4, 4, 5, 5, 5, 7, 7, 8, 8, 8, 9] 
s = 10 
print(sum_target(lst=numbers, target=s)) 
# [(3, (8, 2)), (3, (2, 8)), (6, (5, 5)), (1, (1, 9)), (1, (9, 1))]

來源

2017-06-16 16:15:19

必須有重複和相反的有序對 – joe

好。更新與複製的訂單和兩倍的雙打... –

你確定這個算法是O（N）...通過使用lst.count內循環不會使它O（N^2） – joe

因爲是在評論中提到有一般情況下，沒有O(n)的解決方案，因爲在最壞的情況下你需要輸出n^2對號碼 - 顯然它不能在O(n)時間完成。但對於案件的線性解決方案時，有陣沒有平等的號碼，你只需要使用字典：

numbers = [1, 2, 4, 4, 4, 4, 5, 5, 5, 7, 7, 8, 8, 8, 9] 
tgr = 10 

num2idx = {numbers[i]: i for i in xrange(len(numbers))} 
for i in xrange(len(numbers)): 
    x = numbers[i] 
    y = trg - x 
    if y in num2idx: 
     j = num2idx[y] 
     while j >= 0 and numbers[j] == y: 
      if i != j: 
       print x, y 
      j -= 1

來源

2017-06-16 16:32:51

上面的代碼有多快？這實際上比我的原始速度快嗎？你也說過，如果數組中沒有相同的數字..但是有.. – joe

那麼，它具有複雜性'O（n^2）'，它是最好的，因爲對於最壞的情況（數組[ 5,5,5,5,5]）沒有比O（n^2）更快的算法。雖然這種算法與您的算法具有相同的複雜度，但通常它會更快，因爲它不會浪費時間匹配條件不匹配的對，對於具有所有不同數字的情況，甚至會有線性工作時間。 –

有沒有辦法寫它沒有枚舉關鍵字？我不太熟悉python，並且在理解它到底在做什麼時有點麻煩 – joe

In[50]: numbers 
Out[50]: [1, 2, 4, 4, 4, 4, 5, 5, 5, 7, 7, 8, 8, 8, 9] 
In[51]: expected_result 
Out[51]: 
[[1, 9], 
[2, 8], 
[2, 8], 
[2, 8], 
[5, 5], 
[5, 5], 
[5, 5], 
[5, 5], 
[5, 5], 
[5, 5], 
[8, 2], 
[8, 2], 
[8, 2], 
[9, 1]] 
In[52]: from collections import Counter 
    ...: 
    ...: 
    ...: def matches(nums, target): 
    ...:  cnt = Counter(nums) 
    ...:  result = [] 
    ...:  for num in nums: 
    ...:   diff = target - num 
    ...:   result.extend([[num, diff]] * (cnt[diff] - (diff == num))) 
    ...:  return result 
    ...: 
In[53]: matches(numbers, target=10) == expected_result 
Out[53]: True

來源

2017-06-16 16:54:28

該算法是否有O（N）解決方案？

回答

相關問題