计算时间复杂度为O(nlogn)的列表中的出现次数 [英] Count occurence in a list with time complexity of 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)的列表中的出现次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！