80.Remove Duplicates from Sorted Array II

Tags: [pointer], [trick], [tail], [maintain_tail], [sort], [duplicate]

Com: {fb}

Link: https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/\#/description

Follow up for "Remove Duplicates":
What if duplicates are allowed at mosttwice?

For example,
Given sorted arraynums=[1,1,1,2,2,3],

Your function should return length =5, with the first five elements of nums being1,1,2,2and3. It doesn't matter what you leave beyond the new length.

Solution:

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        counter = 0
        prev = None
        curr = 0
        tail = 0

        while curr < len(nums):
            if prev is None or nums[prev] == nums[curr]:
                counter += 1
            else:
                counter = 1

            if counter > 2:
                prev = curr
                curr += 1
                continue

            nums[tail] = nums[curr]
            prev = curr
            curr += 1
            tail += 1

        return tail

Revelation:

• In Python, prev == 0, 'if not prev' will return True, so here we should use 'if prev is None' or we can initialize prev = -1, then here we check if prev == -1.

Answer Question:

• Question: Each time, we check nums[prev] == nums[curr], and we do nums[tail] = nums[curr], will the nums[tail] = nums[curr] effect the nums[prev] == nums[curr] checking?
• Answer: It will not effect the checking. Because we can think three cases:
• (1) curr and tail are pointing to the same position, then we do nums[tail] = nums[curr], and update prev by curr, so next round prev is pointing to this round's curr, and it is the original value of the nums, it was not overrided.
• (2) prev and tail are pointing to the same position, then we do nums[tail] = nums[curr], and update prev by curr, so next round prev is not pointing to the nums[tail], the prev and curr are both pointing to the 'ORIGINAL' value of the nums.
• (3) tail is on the left side of prev, so they will never effect with each other.

Note:

• Time complexity = O(n), n is the number of elements of the given nums.
• Space complexity = O(1).