граф событие в списке с временной сложностью 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 

Кроме того, вы можете посмотреть на сложность времени v arious операции на другом языке Python объекты here

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 

Получить количество каждого элемента легко с помощью этого метода