My interview question was that I need to return the length of an array that removed duplicates but we can leave at most 2 duplicates.
For example, [1, 1, 1, 2, 2, 3]
the new array would be [1, 1, 2, 2, 3]
. So the new length would be 5. I came up with an algorithm with O(2n) I believe. How can I improve that to be the fastest.
def removeDuplicates(nums):
if nums is None:
return 0
if len(nums) == 0:
return 0
if len(nums) == 1:
return 1
new_array = {}
for num in nums:
new_array[num] = new_array.get(num, 0) + 1
new_length = 0
for key in new_array:
if new_array[key] > 2:
new_length = new_length + 2
else:
new_length = new_length + new_array[key]
return new_length
new_length = removeDuplicates([1, 1, 1, 2, 2, 3])
assert new_length == 5
My first question would be is my algorithm even correct?
Your logic is correct however he is a simpler method to reach the goal you had mentioned in your question.
Here is my logic.
myl = [1, 1, 1, 2, 2, 3, 1, 1, 1, 2, 2, 3, 1, 1, 1, 2, 2, 3]
newl = []
for i in myl:
if newl.count(i) != 2:
newl.append(i)
print newl
[1, 1, 2, 2, 3, 3]
Hope this helps.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With