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

我做了一些研究，发现list.count()的时间复杂度是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)

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

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

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

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

另外，您可能需要查看不同Python对象( 这里 )上各种操作的时间复杂性。

Answer 2

柜台是您的助手：

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

通过此方法可以轻松地获取每个元素的计数。