的错误结果实施与蟒蛇

我试图使用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 –

的错误结果实施与蟒蛇

回答

相关问题