arrays - 计算反转？

Question

我有这段代码可以计算数组中的反转次数。它适用于小型阵列。

但是对于大小超过 500 的数组，该值与正确值相差 20 -50

def merge(left,right):
    result=[]
    i,j,inv=0,0,0
    while i<len(left) and j<len(right):
        if left[i]<right[j]:
            result.append(left[i])
            i=i+1
        else:
            result.append(right[j])
            j=j+1
            inv=inv+len(left)-i 
    result+=left[i:]    
    result+=right[j:]
    return result,inv


def mergesort(li):
    if len(li)<2:
        return li,0
    middle=len(li)//2
    left,invl=mergesort(li[:middle])     
    right,invr=mergesort(li[middle:])
    result,invs= merge(left,right)
    inv=invl+invr+invs
    return result,inv




 if __name__ == '__main__':
    n=int(raw_input())
    ans=[]
    for i in range(n):
        m=int(raw_input())
        li=raw_input().split(' ')
        print len(li)
        result,inversions=mergesort(li) 
        ans.append(inversions)
    for i in range(n):
        print ans[i]    

我错过了什么？

Answer 1

您不需要大型数组来获得错误的反转计数：

>>> mergesort([1,1,1,1])
([1, 1, 1, 1], 6)

您的错误是您将所有相等元素对都视为反转，

if left[i]<right[j]:
    result.append(left[i])
    i=i+1

应该

if left[i] <= right[j]:
    result.append(left[i])
    i=i+1

这样相等的元素就不会被交换并计为倒置。

您收到的短数组不包含重复项，但较大的数组包含。