Question: https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/
Basically, duplicates in a sorted array needs to be removed without creating a new one. I have tested my solution, and it falters when there are 3, 5, 7 (and so on) number of duplicates of the same number. Please give me some insights. I don't know if this is a good place to ask this question, or anywhere else to ask this. Any more related advice is appreciated. Thank you.
Code:
def removeDuplicates(nums):
i = 0 # moving pointer
end = len(nums)-1 # points to the end of the array
# iterates over the array
while i != end:
# if current number is equal to the next
if (nums[i] == nums[i 1]):
# pop it off
nums.pop(i)
# decrement the length of array
end -= 1
i = 1 # increments the moving pointer
return i 1
nums = [0,0,1,1,1,2,2,3,3,4]
print(removeDuplicates(nums))
CodePudding user response:
The way to remove duplicates from a sorted list in O(1) space and O(n) time is to pack the unique elements at the beginning of the list, and then truncate the list:
def removeDuplicates(nums):
#new length
newlen = 0
for val in nums:
if newlen == 0 or nums[newlen-1] != val:
# no matter what, we've already retrieved nums[newlen],
# so this write doesn't interfere with the rest of the loop
nums[newlen] = val
newlen = 1
# delete the unused space at the end of the list, all at once
if newlen < len(nums):
del nums[newlen:]
return newlen
nums = [0,0,1,1,1,2,2,3,3,4]
print(removeDuplicates(nums))
print(nums)
Your original code fails, because you remove elements from the start of the array as you're iterating through the end. The iteration remembers its position in the array in i
, and when you remove an element, the elements after it are shifted into lower positions.
You could fix that by putting the i = 1
into an else
, but the resulting implementation would still take O(N^2) time, which isn't really acceptable.