CODEWITHSUNDEEP
pythonlist
Ewdlam
Ewdlam

Reputation: 935

How to replace all items in a list with their order in python?

Let's take this list :

L = [8,1,4,2]

I would like to replace its elements with their order.
Expected result :

[4,1,3,2]

The following script works but is really unefficient with its double for loop :

L_result = []
for i in L :
    order = 1
    for j in L :
        if i > j :
            order += 1
    L_result.append(order)

Upvotes: 2

Views: 297

Answers (1)

Dani Mesejo
Dani Mesejo

Reputation: 61910

Use sorted + enumerate:

L = [8, 1, 4, 2]

positions = {e: i for i, e in enumerate(sorted(L), 1)}
result = [positions[e] for e in L]

print(result)

Output

[4, 1, 3, 2]

This approach is O(n log n) since is sorting the array. If L have duplicates values, you can do the following:

from collections import defaultdict, deque

L = [8, 1, 4, 8, 2]

positions = defaultdict(deque)
for i, e in enumerate(sorted(L), 1):
    positions[e].append(i)

result = [positions[e].popleft() for e in L]

print(result)

Output

[4, 1, 3, 5, 2]

The reason for using a deque is to make order stable, the first 8 has the first position, while at the same time keeping the popleft operation O(1), therefore the algorithm remains O(n log n).

Upvotes: 3

Related Questions