在有序数组中就地去除超过任意最大重复次数的元素

Posted by daquexian on November 25, 2016

LeetCode第80题,链接戳这里

Follow up for “Remove Duplicates”: What if duplicates are allowed at most twice?

For example, Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

在讨论区里看到的绝妙算法,不仅适用于允许重复次数为两次的情况,而是对任意的次数都适用:

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        k = 2
        for n in nums:
            if i < k or n > nums[i - k]:
                nums[i] = n
                i += 1
        print(nums[:i])
        return i

只需要重新设置k的值,就可以改变允许的最大重复次数