Counting occurrences of elements in Python

Asked Mar 16 '20 at 02:18

Active Mar 16 '20 at 02:18

Viewed 39 times

I need a program that counts the occurrences of elements in a list sorted in non-decreasing order.

Right now, my program looks like:

def list_count(L):
    occ = []
    M = L.copy()
    for i in range(len(L)):
        occ.append(M.count(L[i]))
    return occ

But the issue I have with the is the O(n^2) runtime. If L is sorted in non-decreasing order, is there a way to implement binary searching to bring the runtime down to O(n) or O(logn) without the use of counter?

asked Mar 16 '20 at 02:18

qmack

3

You might be looking for `collections.Counter`. – hilberts_drinking_problem Mar 16 '20 at 02:19
To add to @hilberts_drinking_problem's comment you might consider reading the source code to [that class](https://github.com/python/cpython/blob/3.8/Lib/collections/__init__.py#L489). – kojiro Mar 16 '20 at 02:25
Why don't you want to use a dict? That would bring the complexity down to O(n) – juanpa.arrivillaga Mar 16 '20 at 03:30

Counting occurrences of elements in Python

0 Answers0