Remove common elements between two list with repeated elements

user_9950263 0
Viewed 76

I need your help because I'm a bit stuck with this issue.

I've got two list with repeated elements:

L = [1,2,5,2,4,1,9]
S =[4,2,9,1]

I want to get the "difference" between the two list, as if I do LS = L-S, and the result should be LS = [1,2,5]. I know that l2 will always be a subset of L, thus S will never have a value not present in L.

Note that only one 1 and one 2 has been removed from L, because there was only one 1 and one 2 in S. L can have elements repeated n times, not just 2 times.

Do you know if there's an "easy" way to do this? I wouldn't like to get an O(n^2) program.

Thank you so much!

set python-3.x list python
2 Answers

Use collections.Counter (Python's version of a multi-set)

from collections import Counter

L = [1, 2, 5, 2, 4, 1, 9]
S = [4, 2, 9, 1]

LS = list((Counter(L) - Counter(S)).elements())
print(LS)

Output

[1, 2, 5]

The overall complexity of this approach is O(n).

user_40015920

You can use this:

l = [1, 2, 5, 2, 4, 1, 9]
s = [4, 2, 9, 1]
for i in range(len(l)-1,-1,-1):
    if l[i] in s:
        s.remove(l[i])
        l.pop(i)
print(l)

But i have no idea about its complexity.

user_145119900
Related