Python two-pointer in place solution.


  • 1
    C
    # not in place
    def removeElement1(self, nums, val):
        res, count = [], 0
        for item in nums:
            if item != val:
                res.append(item)
                count += 1
        nums[:] = res
        return count
    
    # not in place    
    def removeElement2(self, nums, val):
        nums[:] = [item for item in nums if item != val]
        return len(nums)
        
    # in place
    def removeElement(self, nums, val):
        l, r, count = 0, len(nums)-1, len(nums)
        while l <= r:
            while l <= r and nums[l] == val:
                l += 1
            while l <= r and nums[r] != val:
                r -= 1
            if l <= r:
                nums[l], nums[r] = nums[r], nums[l]
        for _ in xrange(l):
            del nums[0]
        return count - l

  • 2
    C

    A version which is easier to understand:

    # in place, two-pointer
    def removeElement(self, nums, val):
        l = len(nums)-1
        for i in xrange(l+1):
            if nums[i] == val:
                while l > i and nums[l] == val:
                    l -= 1
                if l == i:
                    return l
                nums[i], nums[l] = nums[l], nums[i]
        return l+1
    

    A shorter in-place version:

     def removeElement(self, nums, val):
        l, r = 0, len(nums)-1
        while l <= r:
            if nums[l] == val:
                nums[l], nums[r] = nums[r], nums[l]
                r -= 1
            else:
                l += 1
        return l
    

    A even shorter in-place version:

    def removeElement(self, nums, val):
        tail = -1
        for i in xrange(len(nums)):
            if nums[i] != val:
                tail += 1
                nums[tail] = nums[i]
        return tail + 1
    

  • 0
    S

    Thanks for your sharing! But I am wondering if you remove the items equal to 'val'? I test it:
    input: [4, 5, 4], 4
    output: 1, nums = [5, 4, 4]


  • 0
    C

    Yes, it should be like this. '5' is what we should maintain, we don't need to pay attention to all the elements behind this value. You can check the description of this problem.


  • 0
    S

    I may misunderstand the meaning of it. I thought we need to remove all items equal to 'val' in place.


  • 0
    S

    But I still can't understand it totally. Could you help me?

    1. remove all instances of that value in place: remove all items equal to 'val' in place?
    2. It doesn't matter what you leave beyond the new length: what that means? input: [4, 5, 4] output: [5, 4, 4]. Those items equal to 'val' still stay at the same array but behind others?

  • 0
    C

    1, you understanding is correct, 2, you understanding is still correct, we don't care the items behind the values we care!


Log in to reply
 

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