Leetcode题库-删除排序数组中的重复项 II（java语言版）_java 一个排序数组 允许最多重复两个元素 用o(1)f复杂度求出去重后数组的新长度

题目描述:

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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 。


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

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
 
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

       这道题和上一道《删除数组中的重复元素1》很相似，不过就是上一题每个元素只能重复一下，这样就有好多的方法，set去重，双指针等。但这一到题，用set明显就不合适了。因为，要求数组中的每个元素可以出现不超过两次。

     上一题请看我的这个博客：https://blog.csdn.net/weixin_37850160/article/details/86599416

      首先的思路:就是仿照上一题用双指针（一个快指针一个慢指针，然后将一个数组看作两个数组。）。上一题的快指针比慢指针快1，而本题则快2，因为可以重复最多两次了。这个地方稍微有点变化，其余的地方和上一题大同小异，当i,j对应元素不相等时，将i对应的元素赋值给‘‘新数组’’对应位置的j，然后让j向后移动一位（自增）

      第二种思路:也使用这种双指针，不过加入一个变量计算重复元素的次数，当次数小于2时（count从0开始），然后就将i-1对应的值赋值给j（原数组对应的位置的值赋值给新数组对应位置的值）。当前后两个元素相等时就将count++,计算次数。否则就是不相等，则将count归0，重新计算重复元素的次数。

      具体看代码：

第一种方法：

        int []a = new int[]{1,1,1,2,2,3};
        第一种方法
          int j=0;
//          一个快指针一个指针（将一个数组看成两个数组，j代表新数组，i代表原数组），从下标为2开始遍历，这样就满足一个数字出现最多2次（因为不管前两个元素是啥，都不能超过2次，所以i从下标为2开始，但慢指针j从0开始和i比较，每一位都和i=2之后的比较，从而等到要求的数组），当i=j(下标对应的值)时跳过，i!=j（下标对应的值）时将当前的 i赋值给，j+2,也就是下标为2开始的位置。（前提这个数组是一个排序好的数组）
          for (int i=2;i<a.length;i++){
              if (a[j]!=a[i]){
                  a[j+2] = a[i];
                  j++;
              }
          }      

  最后返回的是j+2.因为i从2开始，遍历完后，j代表的数组的长度为i-2.所以还要加上2，满足原数组与新数组相同维度。

执行结果：

执行用时：

 第二种方法：

 //第二种方法
        int []nums = new int[]{1,1,1,2,2,3};
        int j = 0;
        int count = 0;
//          还是运用双指针，不过这次i从1开始，
        for (int i = 1; i < nums.length + 1; i++) {
//            判断元素出现的次数，小于2时，才将i-1的值赋值给j，为什么i-1
//            因为i从一开始，j为新数组下标，将原数组第0个元素赋值给新数组
//            0个元素
            if(count < 2){
                nums[j++] = nums[i - 1];
            }
//            当i没有到nums长度时,并且前后两个元素相等时
            if(i != nums.length && nums[i - 1] == nums[i]){
//                让count++,增加那个相同元素的数量.
                count++;
 
            }else{
//                假如不相等则count次数为0
                count = 0;
            }
        }
//返回的是j,因为i从1到nums的长度，j从0到nums的长度减一。
        System.out.println(j);
    }

执行用时:

总结：这道题和上一题（删除元素1）很相似，思路也和上一题很相似，就是双指针法，将一个数组看作两个数组来操作，代码量少，思路清晰，执行效率高。

2018-3-3