使用 DAC 方法计算数组的反转

Question

我正在尝试编写代码以使用 DAC 方法计算数组的反转。下面是我在 Python

中使用的代码

arr=[1,3,5,2,4,6]
n=6
l=0
h=n-1
count=0

def inversions(l,h):
    if(l==h):
        return [arr[l]]

    m=(h+l)//2
    arr1=inversions(l,m)
    arr2=inversions(m+1,h)

    s1=m-l
    s2=h-(m+1)
    mer=[]
    k1=k2=0

    while(k1<=s1 and k2<=s2):
        if(arr1[k1] < arr2[k2]):
            mer.append(arr1[k1])
            k1+=1
        else:
            count+=(k2-(m+1))
            mer.append(arr2[k2])
            k2+=1

    if(k1>s1):
        mer.extend(arr2[k2:s2+1])

    if(k2>s2):
        mer.extend(arr2[k1:s1+1])    

    return mer

res=inversions(l,h)

print('Total No. of Inversions : %d' %count)

在运行上面的代码中，我收到了这条错误消息。

UnboundLocalError: local variable 'count' referenced before assignment

我无法理解这个错误。谁能告诉我为什么会出现此错误？

Answer 1

查看第 26 行的代码。

arr1 = inversions(l, m)

在这一行中，您将分配函数 returns 的值。但是你的函数居然returns？然后想一想，您的列表包含什么类型的内容？当然，'Nonetype'.

然后看到那一行，

if(arr1[k1] > arr2[k2]):

您正在比较，即尝试减去两个 Nonetype 对象，这就是错误的原因。

发生此错误是因为您试图在声明变量之前为其赋值。你可能会说，好吧，我已经在函数外声明了它。如果你想使用全局变量，你必须明确地告诉你这样做，除非它会将它视为函数的局部变量。

要解决您最近的错误，您可以在为函数中的计数赋值之前使用以下行。

global count

但是，我认为您的代码编写得不够完美。它仍然有错误。希望你自己解决它:)

虽然输出错误，但在我的机器上运行非常完美。

def inversions(l,h):

    if(l==h):
        return [arr[l]]

    m=(h+l)//2
    arr1=inversions(l,m)
    arr2=inversions(m+1,h)

    s1=m-l
    s2=h-(m+1)
    mer=[]
    k1=k2=0

    while(k1<=s1 and k2<=s2):
        if(arr1[k1] < arr2[k2]):
            mer.append(arr1[k1])
            k1+=1

        else:
            global count
            count +=(k2-(m+1))
            mer.append(arr2[k2])
            k2+=1

    if(k1>s1):
        mer.extend(arr2[k2:s2+1])

    if(k2>s2):
        mer.extend(arr2[k1:s1+1])

    return mer

res=inversions(l,h)

print('Total No. of Inversions : %d' %count)

使用 DAC 方法计算数组的反转

Counting inversions of an array using DAC approach

python

divide-and-conquer