的錯誤結果實施與蟒蛇

我試圖使用python實現與歸併計數版本計數倒置，這裏是我的代碼：的錯誤結果實施與蟒蛇

def merge(inLeft, inRight): 
    inversions = 0; output = [] 
    while 0 < len(inLeft) and 0 < len(inRight): 
     if inLeft[0] < inRight[0]: 
      output.append(inLeft[0]) 
      inLeft.remove(inLeft[0]) 
     else: 
      output.append(inRight[0]) 
      inRight.remove(inRight[0]) 
      inversions += len(inLeft) 

    if len(inLeft) == 0: 
     output.append(inRight[0]) 
    elif len(inRight) == 0: 
     output.append(inLeft[0])  
    return output, inversions 

def mergeSort(inList): 
    length = len(inList) 
    if length == 1: 
     return inList, 0 
    left, s1 = mergeSort(inList[: length//2]) 
    right, s2 = mergeSort(inList[length//2: ]) 
    sortedList, s3 = merge(left, right) 
    return sortedList, (s1+s2+s3)

我想，當我通過mergeSort([1, 3, 5, 2, 4, 6])調用它，我會得到([1, 2, 3, 4, 5, 6], 3)，但實際上我得到([1, 2, 3, 4], 1)，當我檢查它時，我發現left數組總是<built-in function sorted>。

我正在研究分而治之算法，因此不善於分析遞歸問題。問題在哪裏？我該如何解決它？

來源

2017-08-17 Amarth Gûl

聽起來好像你的實際代碼使用了一個變量'sorted'，它實際上是一個Python中的內置函數。 – quamrana

@quamrana我再次檢查了代碼，確實有一個變量'sorted'，但存在於另一個不參與該過程的函數中。更新了代碼，現在顯示的是完整的腳本。 –

if len(inLeft) == 0: 
    output.append(inRight[0]) 
elif len(inRight) == 0: 
    output.append(inLeft[0])

這隻會將第一個元素添加到輸出。更改爲output.extend(inRight)/output.extend(inLeft)以有效地添加整個陣列。這將修復你缺少的元素。

此外，Python列表的remove操作的複雜性爲O(N)，因此您可能需要考慮使用deque（collections.deque），該列表允許從列表的前端有效地移除。

來源

2017-08-17 10:08:05 astraldawn

您可能誤解了我的意圖，我的工具與其他反轉計數實現有點不同。我去通過2輸入數組，比較元素，傳輸較小的一個輸出數組（所以我'append（）'和'remove（）'）。根據反演的特點，當左側的元素大於右側時，左側的元素數量可以加到反演數量上。此外，感謝'deque'提示：D –

的錯誤結果實施與蟒蛇

回答

相關問題