leetcode每日一题

每日一题的leetcode

删除有序数组重复项II

题目描述：

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

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

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

解题思路：

因为本体不能额外申请数组空间，因此很容易想到需要一个指针来记录满足条件的位置，一个指针用于遍历数组，因此本题采用双指针很容易做出来。

慢指针 slow : 指向当前即将放置元素的位置；则 slow - 1 是刚才已经放置了元素的位置。
快指针 fast : 向后遍历所有元素；
因为最多允许两个重复元素，并且 slow - 2 位置是上上次放置了元素的位置，所以让 nums[fast] 跟 nums[slow - 2] 进行比较。每次都是只允许最多两个元素出现重复，这两个元素的位置在 slow - 1 和 slow - 2。

思路：慢指针即满足题目条件的最大索引（最后满足条件数组的长度），快指针用于遍历数组；这里可以想象慢指针指向的是一个新的数组，我们只需要关心慢指针什么时候增加满足条件的元素，即不重复两次的元素，即nums[slow-2]!=nums[fast]；若满足，则添加新元素nums[slow]=nums[fast]，指针后移slow=slow+1。

#不重复两次的元素class Solution(object):
    def removeDuplicates(self, nums):
        slow=0
        for fast in range(len(nums)):
            if(slow<2 or nums[slow-2]!=nums[fast]):#不重复两次的元素
                nums[slow]=nums[fast]#
                slow=slow+1#指针后移
        return slow

参考：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/solution/fu-xue-ming-zhu-dong-hua-ti-jie-bang-zhu-yrx5/