奇怪的行爲100000個元素

Question

我已經在算法設計加入了斯坦福在線課程，現在我解決第一個編程的問題。

的file包含一些隨機順序1和100000之間 所有100000點的整數（包括兩者）（沒有整數被重複）。您的 任務是查找給定文件中的反轉次數（每行 具有1到100,000之間的單個整數）。假設您的陣列從 1到100,000，並且文件的第i行爲您提供了 陣列的第i個條目。

更新：我發現我的代碼只適用於2^n的情況。問題出在代碼中，而不是Python。我更新了代碼，現在它工作正常，我已經完成了測驗。感謝所有誰幫助

固定碼是：

def merge_count_split (a, b): 
     c = [] 
     inv = 0 
     i=0 
     j=0 
     for k in range(len(a) + len(b)): 
       if i < len(a) and j < len(b): 
         if a[i] < b[j]: 
           c.append(a[i]) 
           i += 1 
         elif a[i] > b[j]: 
           c.append(b[j]) 
           inv += len(a)-i 
           j += 1 
       elif i == len(a): 
         c.append(b[j]) 
         j += 1 
       elif j == len(b): 
         c.append(a[i]) 
         i += 1 
     return c, inv 

def count_inv (data): 
     n = len(data) 
     if n == 1: 
       return data, 0 
     a, x = count_inv(data[:n/2]) 
     b, y = count_inv(data[n/2:]) 
     c, z = merge_count_split(a,b) 
     return c, x + y + z 

with open('IntegerArray.txt') as f: 
     array = [int(line) for line in f] 
     print count_inv(array)[0] 

這一方案對於小陣列工作正常，但是從問題的大陣其打印數字陣列依次，不100000，如我所料。它隨機放置數字。

什麼是蟒蛇的這種異常行爲的原因是什麼？

Answer 1

通過設置n = len(a)並且僅合併n * 2次，如果它長於a，則截斷b。

這部分解釋了驚人的事實，你必須在結果列表2個** 16個項目。