remove duplicates from sorted array LC 28 and LC 88

In theses two problems, we are asked to remove duplicates in place from a sorted array of integer. The difference is the first problem wants only unique number to remain. But the second problem allow us to have 2 duplicates but need to remove the third and beyond. We could generalize this problem to: Remove duplicates that appear more than k times(but keep the (0… k) appearance )

Use a counter to keep track of how many times we have seen the current number. If we see it more than k times, then we know it is a duplicate we need to remove.

Then we iterate through the list from i to len(nums) and compare the ith one with i – 1th element. We need to keep track of a second pointer that points to the place we need to insert the numbers. That second pointer actual_pos will always equal or less than i because if we see a duplicates more than k time in one iteration, we won’t increment actual_pos(the second pointer). And we know later if we see a non-duplicate number, we need to put it at nums[actual_pos], overwriting the duplicate.
Rendered by QuickLaTeX.com

def removeDuplicates(self, nums, k):
    if not nums: return 0
    actual_pos = 1
    count = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            count += 1
            if count > k:
                continue
        else:
            count = 1

        nums[actual_pos] = nums[i]
        actual_pos += 1
    return actual_pos

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax