нахождение инверсий числового массива с использованием разделяй и властвуй - PullRequest
Новая
       26

нахождение инверсий числового массива с использованием разделяй и властвуй

0 голосов
/ 27 марта 2012

Я натолкнулся на пост в SO , где алгоритм реализован в коде Python. Это прямая реализация псевдокода в этой статье .

Однаков псевдокоде есть строка, в которой число увеличивается на количество оставшихся элементов в массиве 'a'. В приведенном выше коде Python он задан как 

count += len(a) - i

мы не можем сделатьто же самое по 

count += len(a[i:])

Кроме того, вместо 

c += a[i:] + b[j:]

Я написал, 

c.append(a[i:])
c.append(b[j:])

В целом моя версия выглядит так 

def merge(left,right):
    i=0
    j=0
    count=0
    c=[]
    while i<len(left) and j<len(right):
        c.append(min(left[i],right[j]))
        if right[j]< left[i]:
            count+=len(left[i:])
            j+=1
        else:
            i+=1
    c.append(left[i:])
    c.append(right[j:])
    return count,c


def dnc(input):
    if len(input)==1:
        return 0,input
    mid=len(input)/2
    left=input[:mid]
    right=input[mid:]
    l,left=dnc(left)
    r,right=dnc(right)
    m,result=merge(left,right)
    count=l+r+m
    return count,result

Увы!, Когда я вычисляю это в отсортированном массиве, я получаю 3 вместо 0 

if __name__=='__main__':
    input =[1,2,3,4,5]
    ct,res=dnc(input)
    print ct

Что я сделал не так?Может кто-нибудь помочь мне узнать?

1 Ответ

6 голосов
/ 27 марта 2012

Вот что я могу предложить:

  • Не делай count += len(a[i:]).Это медленнее, чем ваш оригинал, и излишне усложняет логику.Вместо этого я бы кэшировал len(a) как len_a и вычислял бы его один раз за пределами вашего цикла, так как a, похоже, не изменяется.

  • c += a[i:] + b[j:] - это то же самоекак c.extend(a[i:]) и c.extend(b[j:]).extend добавляет содержимое списка к c, а append добавляет сам список, что может быть причиной вашей проблемы.

...