Number of samples in a list with O (nlogn) time complexity

Question

This is what I still have:

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), so this code will be O (n ^ 2).

Is there a way to reduce this to O (nlogn)?

Answer 1

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

 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 

Alternatively, you can look at the time complexity of various operations on various Python objects here.

Answer 2

The counter is your assistant:

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

Get the counter of each item using this method