class Solution: # @param a list of integers # @return an integer def removeDuplicates(self, A): if not A: return 0 newTail = 0 for i in range(1, len(A)): if A[i] != A[newTail]: newTail += 1 A[newTail] = A[i] return newTail + 1
duplicate num will be overridden if its index is less than newTail, otherwise it remains in the original array since in the problem description it says:
It doesn't matter what you leave beyond the new length.
Sorry, I didn't read your code carefully. Now I find out how it works. Can you help me figure out why I got an output limit error? Thx a lot.
class Solution: ''' @param integer nums @return integer ''' def removeDuplicates(self, nums): i = 0 while i < (len(nums) - 1): if nums[i] is nums[i+1]: del nums[i] else: i += 1 return len(nums)
Most likely because of the
del nums[i] - it is an O(n) operation. Your code has a worst run time of O(n^2).
Thanks for your sharing! I tried your solution, and it was accepted, but I still have a question:
input: nums = [1, 2, 1], output: 3, [1, 2, 1].
I think it should be 2 instead of 3?
@yulin_ we are given a sorted array in this problem, and so nums = [1,2,1] is illegal
why this code doesn't accepted?
@AaronWuu note that "Do not allocate extra space for another array, you must do this in place with constant memory", so we should change the element order in nums
@wjymath do you mean when we use function "set", we are actually creating a new array?
@bdeng3 yeah~ notice the doc of set below
| set() -> new empty set object
| set(iterable) -> new set object
@wjymath Yeah, I just checked it as you suggested, thanks for the explanation!
Modified Ur amazing code to remove the duplicated, though not require for the problem
def removeDuplicates(self, nums):
newTail=0 for i in range(1,len(nums)): if nums[i]!=nums[newTail]: newTail+=1; nums[newTail]=nums[i] for j in range((newTail+1),len(nums)): nums.pop(-1) return len(nums),nums
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.