Simple Python solution - O(n)


  • 24
    G
    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

  • 1
    J

    Did you remove the duplicated num from nums?


  • 1
    G

    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.
    

  • 1
    J

    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)

  • 6
    G

    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).


  • 0
    Z

    you should control the len of the while loop


  • 0
    9
    This post is deleted!

  • 0
    9
    This post is deleted!

  • 0
    Y

    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?


  • 0
    W

    @yulin_ we are given a sorted array in this problem, and so nums = [1,2,1] is illegal


  • 3
    A

    why this code doesn't accepted?
    '''
    def removeDuplicates(self,nums):
    return len(set(nums))
    '''


  • 0
    W

    @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


  • 0
    B

    @wjymath do you mean when we use function "set", we are actually creating a new array?


  • 2
    W

    @bdeng3 yeah~ notice the doc of set below
    class set(object)
    | set() -> new empty set object
    | set(iterable) -> new set object


  • 0
    B

    @wjymath Yeah, I just checked it as you suggested, thanks for the explanation!


  • 0
    J

    Modified Ur amazing code to remove the duplicated, though not require for the problem
    '''
    class Solution(object):
    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
    

    print(Solution().removeDuplicates([1,1,2,3,5,6,6]))

    '''


  • 0
    A
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.