本文介绍了计算时间复杂度为O(nlogn)的列表中的出现次数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

这是我到目前为止所拥有的:

This is what I have so far:

alist=[1,1,1,2,2,3,4,2,2,3,2,2,1]
def icount(alist):
    adic={}
    for i in alist:
        adic[i]=alist.count(i)
    return adic

print(icount(alist))

我做了一些研究,发现list.count()的时间复杂度为O(n),因此,此代码将为O(n ^ 2).

I did some research to find out that the time complexity of list.count() is O(n), thus , this code will be O(n^2).

有没有办法将其减少为O(nlogn)?

Is there a way to reduce this to O(nlogn)?

推荐答案

您可以像这样使用Counter

from collections import Counter
alist=[1,1,1,2,2,3,4,2,2,3,2,2,1]
print Counter(alist)

如果您想使用自己的解决方案,则可以像这样改善它

If you want to use your solution, you can improve it like this

def icount(alist):
    adic = {}
    for i in alist:
        adic[i] = adic.get(i, 0) + 1
    return adic

更好的是,您可以像这样使用defaultdict

Even better, you can use defaultdict like this

from collections import defaultdict
adic = defaultdict(int)
for i in alist:
    adic[i] += 1
return adic

此外,您可能希望查看不同Python对象上各种操作的时间复杂度此处

Also, You might want to look at the Time Complexity of various operations on different Python objects here

这篇关于计算时间复杂度为O(nlogn)的列表中的出现次数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

10-26 21:49