Leetcode-80 删除排序数组中的重复项 II(最详细解答)_删除有序数组中的重复项

Leetcode-80
删除排序数组中的重复项 II

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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；
初始状态下，慢指针应紧随快指针之后，因此初始值为 1；

结束条件：
快指针达到数组结尾。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if(n <= 2)
        {
            return n;
        }
        int sp = 1;
        for(int fp = 2; fp < n; fp++)
        {
            if(nums[fp] != nums[sp - 1])
            {
                nums[++sp] = nums[fp];
            }
        }
        return sp + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19