奇怪的行为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个项目。