Подсчет инверсий массива с использованием подхода ЦАП

Question

Я пытаюсь закодировать подсчет инверсий массива с использованием подхода ЦАП. Ниже приведен код, который я использую в 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) 

В этой строке вы присваиваете значение, что функция возвращает. Но какова ваша функция на самом деле? Тогда подумайте, какой контент содержится в вашем списке? Определенно, «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)