在时间复杂度为O（nlogn）的列表中计数发生次数

Question

到目前为止，我得到的是：

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))

我做了一些研究发现列表.计数（）是O（n），因此，此代码将是O（n^2）。在

有没有办法把它减到O（nlogn）？在

Answer 1

您可以像这样使用Counter

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

如果你想使用你的解决方案，你可以这样改进它

^{pr2}$

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

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

另外，您可能需要了解不同Python对象上的各种操作的时间复杂性here