合併排序2列表查找通用元素

Question

對於一個賦值，我們被要求編寫一個函數，它將輸入2個列表作爲輸入，然後返回一個包含'列表1'和'列表2'中所有名稱的列表。

它被要求使用基於合併排序的算法來完成。到目前爲止，我所得到的結果都會返回正確的列表，但是我正在進行太多比較以獲取此列表。 VoterList是給予我們的指定類，以便我們不使用普通的Python列表。只有VoterName對象（由兩個輸入列表組成）能夠被附加到VoterList。通過的名單都是按字典順序排列的。

歡迎任何關於如何減少比較的建議。謝謝。

from classes import VoterList 
def fraud_detect_merge(first_booth_voters, second_booth_voters): 

    fraud = VoterList() 
    length_first = len(first_booth_voters) 
    length_second = len(second_booth_voters) 
    first_booth_position = 0 
    second_booth_position = 0 
    comparisons = 0 
    while first_booth_position < length_first: 

     if second_booth_position == length_second: 
      first_booth_position += 1 
      second_booth_position = 0 

     else: 
      name_comparison = first_booth_voters[first_booth_position] 
      comparisons += 1 

      if second_booth_voters[second_booth_position] == name_comparison: 
       fraud.append(second_booth_voters[second_booth_position]) 
       first_booth_position += 1 
       second_booth_position = 0 

      else: 
       second_booth_position += 1 


    return fraud, comparisons 

Answer 1

不清楚你的輸入是什麼，它已經排序？你正在獲得名單。查看可以在列表上執行哪些操作，您將找到pop()操作。這會從列表中刪除一個項目併爲您提供其價值。由於名單都是爲了下面的方法可以用來：

def fraud_detect_merge(first_booth_voters, second_booth_voters): 
    fraud = VoterList() 
    comparisons = 0 

    first_booth_voters.sort()  # if not already sorted 
    second_booth_voters.sort() # if not already sorted 

    first = first_booth_voters[0] 
    second = second_booth_voters[0] 

    while first_booth_voters and second_booth_voters: 
     comparisons += 1 

     if first == second: 
      fraud.append(first) 
      first = first_booth_voters.pop(0) 
      second = second_booth_voters.pop(0) 
     elif first < second: 
      first = first_booth_voters.pop(0) 
     else: 
      second = second_booth_voters.pop(0) 

    return fraud, comparisons 

Answer 2

分配究竟會詢問你找到一個解決方案，並有合併排序的大提示，所以我不會濺出出來爲你找出答案:)但是，也許我可以指出所發生的事情在你的代碼：與你的while循環，你已經基本上完成長度length_first在最壞的情況下，兩個嵌套循環和length_second：

for name_comparison in first_booth_voters: 
    for second_name in second_booth_voters: 
    comparisons += 1 
    if second_name == name_comparison: 
     fraud.append(second_name) 
     break 

導致在最壞的情況下比較length_first x length_second。鑑於輸入列表已排序，這當然不是最佳的。您需要利用分類。如果輸入列表沒有排序，則應考慮用更易讀的嵌套for循環替換難以閱讀/調試/理解while循環。