0

我在 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

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

4

1 回答 1

6

这是我可以建议的：

  • 不要做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追加列表本身，这可能会导致您的问题。

于 2012-03-27T03:33:53.170 回答