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

来源Leetcode第80题删除排序数组中的重复项II

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
你不需要考虑数组中超出新长度后面的元素。

第一反应是新建一个表，按顺序记录下排序数组中对应数字出现的次数，但是发现题目要求空间负责度为O(1)，那么则可以简化一下思路，采用两个指针，一个记录当前要修改部位，一个保持向后遍历数组，当有两个连续的数字重复的时候就要进行判断，先保存当前val，然后再复制两个重复的元素，接着指针i开始跳过多余的重复元素即可。
代码如下：

public int removeDuplicates(int[] nums) {
    int m = 0;
    for (int i = 0; i < nums.length;) {
        if (i < nums.length - 1 && nums[i] == nums[i + 1]) {
            int val = nums[i];  //记录当前值
            nums[m++] = nums[i++]; //对数组进行两次操作
            nums[m++] = nums[i++];
            while (i < nums.length && nums[i] == val) //如果2个数之后的数据元素仍与之前相等就跳过
                i++;
        } else
            nums[m++] = nums[i++];  //最后两个元素无所谓从不重复，直接复制就完事了
    }
    return m;
}

在附上一个评论区比较秀的代码：

public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int n : nums)
            if (i < 2 || n > nums[i-2])
                nums[i++] = n;
        return i;
    }

当i<2时，前两项直接复制就好，从第三项开始，如果数组里的n>nums[i-2],说明当前元素和前面复制的不等，拓展开来复制前K个重复的数字就可以把i-2替换成i-K。