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