leetcode:26&80 Remove Duplicates from Sorted Array 删除数组中的重复元素

喜欢ヅ旅行 2022-05-31 08:35 58阅读 0赞

# leetcode:26 #

**对数组元素进行去重，使得原数组重复元素最多保留1个**  
**限制:**  
我们不可以额外分配数组，必须保持空间复杂度为O(1)  
这个并不难实现：

class Solution(object):
        def removeDuplicates(self, nums):
            """ :type nums: List[int] :rtype: int """
            if len(nums) == 0:
                return 0
            k = 0
            for i in range(1, len(nums)):
                if nums[k] != nums[i]:
                    k += 1
                    nums[k] = nums[i]
            return k + 1

我们也可以使用python的特性实现该功能，十分精辟：

class Solution2(object):
        def removeDuplicates(self, nums):
            """ 利用python属性 :type nums: List[int] :rtype: int """
            nums[:] = sorted(set(nums))
            return len(nums)

# leetcode 80 #

**对数组元素进行去重，使得原数组重复元素最多保留2个**

class Solution(object):
        """ 对数组元素进行去重，使得原数组重复元素最多保留2个 """
        def removeDuplicates(self, nums):
            """ :type nums: List[int] :rtype: int """
            if len(nums) <= 2:
                return len(nums)
    
            i, j, cnt = 1, 1, 1
            while j < len(nums):
                if nums[j] != nums[j - 1]:
                    cnt = 1
                    nums[i] = nums[j]
                    i += 1
                else:
                    if cnt < 2:
                        nums[i] = nums[j]
                        i += 1
                        cnt += 1
                j += 1
            return i
    
        def removeDuplicates2(self, nums):
            """ very short code :param nums: :return: """
            i = 0
            for n in nums:
                if i < 2 or n > nums[i - 2]:
                    nums[i] = n
                    i += 1
            return i

# 问题来了：如果使得原数组重复元素最多保留k个 #

class Solution1(object):
        """ 对数组元素进行去重，使得原数组重复元素最多保留k个 """
        def removeDuplicates(self, nums, k):
            """ :type nums: List[int] :rtype: int """
            if len(nums) <= k:
                return len(nums)
    
            i, j, cnt = 1, 1, 1
            while j < len(nums):
                if nums[j] != nums[j - 1]:
                    cnt = 1
                    nums[i] = nums[j]
                    i += 1
                else:
                    if cnt < k:
                        nums[i] = nums[j]
                        i += 1
                        cnt += 1
                j += 1
            return i
    
        def removeDuplicates2(self, nums, k):
            """ very short code :param nums: :return: """
            i = 0
            for n in nums:
                if i < k or n > nums[i - k]:
                    nums[i] = n
                    i += 1
            return i