['a', 'c','a','b','b'] -> ['a', 'c', 'b']
Searching online didn't help. I'm not sure whether this is even possible.
Preferably write solution in Python, but anything is fine.
=====
Edit: I originally said O(1) space, but I don't think it's possible.
Changing the requirements:
No space requirements, but you must modify the input in-place and return it.
How about this? I think the time complexity and the space complexity are both O(n).
def unique(arr):
index = 0
s = set()
for i in range(len(arr)):
if arr[i] not in s:
arr[index] = arr[i]
index += 1
s.add(arr[i])
arr[index:] = []
I don't think this is possible in O(n) time and O(1) space. To get O(n) time you have to have a scratchpad (with O(1) insert and lookup, e.g. a set) recording all the elements you've already seen; that requires O(m) space (where m is the number of unique elements). Conversely, to get O(1) space you have to rescan earlier elements in the array for each element, which is O(n2) time.
If you'll accept an O(m) scratchpad, this fulfills the "modify the array in place" requirement and runs in O(n) time.
def remove_duplicates(arr):
"""Remove all duplicated elements from ARR in O(m) space and O(n) time.
ARR is modified in place and is not returned (like `sort`)."""
n = len(arr)
if n <= 1: return
seen = set((arr[0],))
i = 1
j = 1
while i < n:
if arr[i] not in seen:
seen.add(arr[i])
arr[j] = arr[i]
j += 1
i += 1
del arr[j:i]
This would still be O(n2) time if I deleted elements from the array as I iterated over it, because del arr[i] is itself an O(n) operation: it has to slide everything after i down one. del arr[j:i] where i is past the end of the array should be O(1), but if it really matters, you'd have to check the implementation.
And if you must have O(1) space, here's the O(n2) time algorithm:
def remove_duplicates_quadratic(arr):
"""Remove all duplicated elements from ARR in O(1) space and O(n²) time.
ARR is modified in place and is not returned (like `sort`)."""
n = len(arr)
i = 0
while i < n:
for j in range(i):
if arr[j] == arr[i]:
del arr[i]
n -= 1
break
else:
i += 1
I'm doing manual array indexing in these because deleting elements from an array you're iterating over using any of the usual for..in constructs is unsafe. You could use a for..in loop in the first one, but you'd lose parallel structure so it would be less readable.
In case you haven't seen it before, an else clause on a loop is executed only if the loop is not exited via break.
from collections import OrderedDict
OrderedDict.fromkeys(my_array).keys()
pip install oset
import oset
ll = oset.oset(['a', 'c','a','b','b'])
print(ll)
OrderedSet(['a', 'c', 'b'])`
To keep the speed efficient, you need to use O(n) space to record records that already exist. If there are a large amount of duplicates it won't take much space. However, the del operation on a standard array is O(n) because it has to shift all the following elements.
def uniquify(data):
used = set()
i = 0
while i < len(data):
if data[i] in used:
del data[i] # or data.pop(i)
else:
used.add(data[i])
i += 1
return data # not strictly necessary because array is modified in-place
O(n) time, O(n) space
uniqueList = []
index = 0
while index < len(myList):
item = myList[index]
if item not in uniqueList: uniqueList.append(item)
else: myList.pop(index)
index += 1
Note: Do not modify a list you are iterating through like below:
for index, item in enumerate(myListCopy):
if item not in uniqueList: uniqueList.append(item)
else: myList.pop(index)
O(n^2) time, O(1) space It certainly is bounded by n^2, but in reality it's less.
index = 0
while index < len(myList):
subIndex = index + 1
while subIndex < len(myList):
if myList[subIndex] == myList[index]: myList.pop(subIndex)
subIndex += 1
index += 1
O(n) time, O(1) space If your list is sorted and you don't mind removing the first duplicates.
for item in myList:
if myList.count(item) > 1: myList.remove(item)
lst1= ['a', 'c','a','b','b'] #-> ['a', 'c', 'b']
lst2 = []
for l in lst1:
if l not in lst2:
lst2.append(l)
print lst2
