我正在做一个hackerrank挑战来计算倒数,但我无法通过几个测试用例,因为它说超时。我在我的系统上运行测试用例,大约需要 10 秒才能得到正确的结果。
这是代码:
def merge_sort_inversion(listA):
n=len(listA)
if n==1 or n==0:
return listA,0
left_subArray=listA[:n/2]
right_subArray=listA[n/2:]
left_subArray, left_inversion=merge_sort_inversion(left_subArray)
right_subArray,right_inversion=merge_sort_inversion(right_subArray)
sorted_list, split_inversion=merge_inversion(left_subArray,right_subArray)
return sorted_list,left_inversion+right_inversion+split_inversion
#sorted_list=[]
def merge_inversion(left,right):
sorted_list=[]
count=0
if len(left)==0 or len(right)==0:
return left+right,0
i=0
j=0
for k in range(len(left)+len(right)):
if len(left)!=i and len(right)!=j:
if left[i]>right[j]:
sorted_list.append(right[j])
count=count+len(left[i:])
#print right[j], left[i:],count
j=j+1
else:
sorted_list.append(left[i])
i=i+1
elif len(left)==i:
return sorted_list+right[j:],count
elif len(right)==j:
return sorted_list+left[i:],count
return sorted_list,count
t = int(raw_input().strip())
for a0 in xrange(t):
n = int(raw_input().strip())
arr = map(int, raw_input().strip().split(' '))
a,b=merge_sort_inversion(arr)
print b
有人可以建议吗?
这条线很慢:
count=count+len(left[i:])
因为它从位置 i 向上从左侧的所有元素生成一个新列表。
由于您只需要结果长度,因此您可以通过以下方式更快地完成此操作:
count += len(left) - i
在我的计算机上,这将具有 100,000 个元素的数组的时间从 7.5 秒减少到 0.5 秒。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句