Cancelling out duplicates in a list by even parity-CodePudding

Let's say we have a list such that list = ["1", "2", "1", "3", "1" "3", "4", "3"]

I need a way to remove any duplicates and cancel them out in case there is a total even number of those duplicates. Otherwise, if there is an odd number, only one element would remain. For example, our list would filter to ["2", "3", "4"]

In my case, this list would initially be empty elements added during runtime. I need little time complexity as this list is used in real time for drawing shapes (trying my luck in pygame).

I came across this potential solution to my problem:

def my_function(x):
  return list(dict.fromkeys(x))

mylist = my_function(["a", "b", "a", "c", "c"])
print(mylist) #from https://www.w3schools.com/python/python_howto_remove_duplicates.asp

I can't get my head around how to implement this cancelling out without overcomplicating it. Thank you for reading.

CodePudding user response：

Here is a solution that should work for your case:

def remove_duplicates(lst):
    result = []
    counts = {}
    for elem in lst:
        if elem in counts:
            counts[elem]  = 1
        else:
            counts[elem] = 1
    for elem, count in counts.items():
        if count % 2 == 1:
            result.append(elem)
    return result

lst = ["1", "2", "1", "3", "1", "3", "4", "3"]
result = remove_duplicates(lst)
print(result)

This solution first counts the number of occurrences of each element in the list using a dictionary. Then, it iterates through the dictionary and appends elements with an odd number of occurrences to the result list. This should give you the desired behavior of cancelling out even occurrences of duplicates and keeping only one element if there are an odd number of duplicates.

This solution should have a time complexity of O(n) because it iterates through the list once to count the occurrences and then again to process the counts. This should make it suitable for use in real-time applications.

CodePudding user response：

Using Counter..!

Counter - A subclass of dict that's specially designed for counting hashable objects in Python / occurences of the objects.

Code: Time-O(n) Space-O(n)

from collections import Counter
lis = ["1", "2", "1", "3", "1" , "3", "4", "3"]

a=Counter(lis)
res=[]
for key,value in a.items():
    if value%2!=0:
        res.append(key)
print(res)

Output:

['1', '2', '3', '4']

I think you made a typo in first example output.. 1 should also added cause 1 occurence is odd..

Below code by dictionary..! Time- O(n) Space-O(n)

Code:

lis = ["1", "2", "1", "3", "1" , "3", "4", "3"]
dic,res={},[]

for num in lis:
    dic[num]=dic.get(num,0) 1
    
for key,value in dic.items():
    if value%2!=0:
        res.append(key)
print(res)  #Same output.

CodePudding user response：

Create a set that keeps track of all of the items that have occurred an odd number of times. Iterate over the items in your input list : if the item is in the set already, then remove it. Otherwise add it.

items = ["1", "2", "1", "3", "1", "3", "4", "3"]

theSet=set()
for i in items:
    if i in theSet:
        theSet.remove(i)
    else:
        theSet.add(i)

print(theSet)

I think that you have a small bug in your input data - you're maybe missing a comma after the third "1".

CodePudding user response：

If you mean to cancel out the duplicates, similar to what you stated in your title, meaning that if the occurrence is odd, one occurrence of the number remains; if the occurrence is even, remove all occurrences of the number.

I think the input should contain four "1"'s. Or the output should be ['1', '2', '3', '4'].

You need to edit the question so that the input and the output are not contradictory to each other.

Use collections.Counter() and a list comprehension:

from collections import Counter

list_ = Counter(["1", "2", "1", "3", "1", "3", "4", "3"])  # with three "1"
res = [k for k, v in list_.items() if v % 2 == 1]
print(res)

Output:

['1', '2', '3', '4']