如何改进我的代码以处理大数字?

n0unc3

我正在做一个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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

Python 在处理大数字/列表时是否有问题,或者我的代码有问题吗?

如何改进我的“if and else if”VBA?代码

如何改进我编写的 ramda 代码?

Java:我如何改进这个代码?

如何在Haxe中处理大数字?

如何优化/加速此代码,以便我可以处理大数据集?

我的代码的复杂程度如何,我该如何改进?

为什么我的代码无法处理大数组输入(> 10000)?

片段:如何改进代码?

如何使用面向协议的编程来改进我的Swift代码?

我们如何改进此代码以获得更好的性能

如何改进我的代码,为什么它不运行?

如何改进我的 plsql 代码以使其正常工作?

检查 ID 是否存在(如何改进我的代码)

Python-具有相同数字的下一个更大数字-Codewars Kata-如何改进它

处理大数据时如何确保代码按预期工作?

我该如何改进?

我如何读取textView结尾处的任意大数字?

如何让 Scala 处理大数

我的 Keras CNN 返回相同的输出值,我该如何修复/改进我的代码

Python:如何改进重复代码?

如何改进或优化这段代码

为什么我的代码真的很慢,我该如何改进它?

如何纠正/改进我的 CNN 模型?如何处理验证精度冻结问题?

如何改进我的导航栏?

如何改进我的优化算法?

需要改进我的javascript代码功能

改进我的 C 编码并查找代码问题

如何将Swift可选NSNumber转换为可选Int?(我的代码有任何改进吗?)