使用分而治之的方法找到一个数组的反转

Question

我在SO中发现了一个帖子,其中算法是用python代码实现的.这是本文中伪代码的直接实现.

但是,在伪代码中,有一行,其中count由数组'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

我做错了什么？有人可以帮我找出来吗？

Answer 1

这是我可以建议的:

• 不要这样做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附加列表本身,这可能会导致您的问题.