[split] Time Complexity of Counting

[Gribouillis]

The following code has complexity O(n log(n)) like sorting

import itertools as itt
import operator as op

def solve(problem):
    es = sorted((x, i) for i, x in enumerate(problem))
    t = sorted((x[1], i)
         for k, g in itt.groupby(es, key = op.itemgetter(0))
         for i, x in enumerate(g, 1))
    return [x[1] for x in t]

if __name__ == '__main__':
    problem = [48,52,55,48,52,55,60,62,48]
    expected = [1,1,1,2,2,2,1,1,3]
    assert solve(problem) == expected

Of course, you can reach the same asymptotic complexity by using a sorted dictionary based on binary search instead of the dict class. This module probably provides the needed SortedDict class.

But here, we do it with the standard library alone! For most practical purposes, the dict based solution is probably the best one although it's not O(n log(n))