**80. Remove Duplicates from Sorted Array II 删除排序数组中的重复项 II

1. 原始题目

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定 nums = [1,1,1,2,2,3],

函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,1,2,3,3],

函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。

你不需要考虑数组中超出新长度后面的元素。

2. 思路

由于数组是已经排序的，所以可以利用这一条件。因为要求每个数最多重复2次。所以如果当前数据长度小于等于2，则不动，i指针往前走。如果大于2的数组，当前的元素如果比其前面的第二个数大则一定可以加入。

3. 解题

 class Solution:

     def removeDuplicates(self, nums: List[int]) -> int:

         i = 0    # 后端索引

         for n in nums:    # 对于每个元素

             if i<2 or n>nums[i-2]:   # 如果元素数目<2则直接加入，如果当前元素比前面第2个元素大，则说明不重复，予以加入

                 nums[i] = n

                 i+=1

         return i

4. 总结

26. Remove Duplicates from Sorted Array 是此题型的第一题：

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

即【1，1，2，3，5，7，7，8】返回6 ，因为【1，2，3，5，7，8】。思路仍然是一样的。什么时候当前元素可以放到前面去？如果元素长度<1肯定可以直接放。那此外如果当前元素比i指向的元素大，说明没有重复也可以直接放入！

class Solution:

    def removeDuplicates(self, nums: List[int]) -> int:

        i = 0

        for n in nums:

            if i<1 or n>nums[i-1]:

                nums[i] = n

                i+=1

        return i

巴特西

**80. Remove Duplicates from Sorted Array II 删除排序数组中的重复项 II

1. 原始题目

2. 思路

3. 解题

4. 总结

最新文章

热门文章