0

我在 pyhton 中制作了一个计数反转程序，并使用 python27 来实现。我已经使用分而治之的技术（合并排序技巧）实现了算法。我的程序对于大小为 100 的输入数组运行良好（这是我可以验证的最大值）。现在我在大小为 50,000 和 1,00,000 的输入数组上测试了我的程序，但是我怎么也无法得到正确的答案。我在下面粘贴了我的代码，请指出任何可能的错误：

    f=open('forum.txt')
    a=[]
    s=1
    for line in f:
        a.append(line)





def CountInversion(IntegerArray):
_count=0
lc=0
rc=0
RightArray=[]
LeftArray=[]
if len(IntegerArray)>1:
        LeftArray,lc=CountInversion(IntegerArray[:len(IntegerArray)/2])
        RightArray,rc=CountInversion(IntegerArray[len(IntegerArray)/2:])
elif len(IntegerArray)==1:
    return IntegerArray,0
ResultArray=IntegerArray
i=0
l=len(ResultArray)
j,k=0,0
for i in range(0,l):
    if j<len(RightArray) and k<len(LeftArray):
        if RightArray[j]<LeftArray[k]:
            ResultArray[i]=RightArray[j]
            j += 1
            a=(len(LeftArray)-k)
            _count = _count + a    
        else:
            ResultArray[i]=LeftArray[k]
            k += 1
elif j<len(RightArray):
    ResultArray[i]=RightArray[j]
        j += 1
elif k<len(LeftArray):
        ResultArray[i]=LeftArray[k]
        k += 1          
return ResultArray,(_count+lc+rc)

arr,b=CountInversion(a)

print ('end of inversions')

print b

我还运行了 JF Sebastian 在这篇文章中给出的代码，但结果是相同的（答案对于小输入是正确的，但对于大小为 50000 或 1,00,000 的输入数组则不正确）

4

2 回答 2

0

您的第一个问题是缩进不一致。在几行中，您使用制表符而不是空格，这是一个非常糟糕的主意。缩进在 Python 中很重要，所以如果不小心很容易出错。

我认为您遇到的第二个问题是您正在比较字符串，而不是数字。Python 非常乐意对字符串进行排序，但它会使用字典顺序排序，这在应用于编码为字符串的整数时可能会出乎意料。例如， string"11"将排在 string 之前"2"，因为它的第一个字符1在2ASCII 字符集中（以及在 Unicode 中）之前。

正如我在评论中所问的那样，尚不清楚您如何确定您的代码无法正常工作。简单地解决我上面描述的问题可能会解决您遇到的问题。如果他们不这样做，请解释您如何确定您的结果无效，我将尝试更新这篇文章并提供进一步的建议。

于 2013-02-09T03:48:53.287 回答
0

通过将字符串解析为 int 并填充数组来解决问题

于 2013-10-01T19:57:42.990 回答