在时间复杂度为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

计数器是您的助手：

>>> from collections import Counter
>>> a = [1,2,1,3,4]
>>>  Counter(a)
Counter({1: 2, 2: 1, 3: 1, 4: 1})
>>> x = Counter(a)     
>>> x[1]
2
>>> x[2]
1

通过这个方法可以很容易地得到每个元素的计数

Answer 2

您可以像这样使用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