Count occurence in a list with time complexity of O(nlogn)

list, python, python-3.x

Solution

You can use `Counter` like this

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

Even better, you can use `defaultdict` like this

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

Also, You might want to look at the Time Complexity of various operations on different Python objects here

Problem

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)) ``` 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). Is there a way to reduce this to O(nlogn)?

Original source