計算反演？

Question

我有這個代碼來計算數組中的反轉次數。 它適用於小型陣列。

但對於規模超過500的陣列，該值從正確的價值

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]  

它是什麼，我缺少相差20℃-50℃

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 

這樣，相等的元素就不會被交換和計算爲倒數。

您收到的短陣列不包含重複項，但是較大的那個沒有。