一、问题

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

示例 1：
给定数组 nums = {1,1,2}
方法应该返回新的长度 2，并且原数组 nums 的前两个元素被修改为 1 和 2。

示例 2：
给定 nums = {0,0,1,1,1,2,2,3,3,4}
方法应该返回新的长度 5，并且原数组 nums 的前五个元素被修改为 0、1、2、3 和 4。

二、解答

测试主类：

public static void main(String args[]) {
    int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    TestDemo testDemo = new TestDemo();
    testDemo.removeDuplicates(nums);
}

1️⃣双指针法

数组是有序的，重复的元素一定会相邻。要求删除重复元素，实际上就是将不重复的元素移到数组的左侧。可以放置两个指针 p 和 q，其中 p 是慢指针，而 q 是快指针。算法流程如下：

1. 比较 p 和 q 位置的元素是否相等。
2. 如果相等，q 后移一位。如果不相等，将 q 位置的元素复制到 p+1 位置上，p 后移一位，q 后移一位。
3. 重复上述过程，直到 q 等于数组长度。返回 p + 1，即为新数组长度。
4. 说明：如图此时数组中没有重复元素，每次比较 nums[p] 都不等于 nums[q]，因此就会将 q 指向的元素原地复制一遍，这个操作其实是不必要的。因此可以添加一个小判断，当 q - p > 1 时，才进行复制。

q-p>1

public int removeDuplicates(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int p = 0;
    for (int q = 1; q < nums.length; q++) {
        if (nums[q] != nums[p]) {
            p++;
           if(q - p > 1){
             nums[p] = nums[q];
            }
        }
    }
    return p + 1;
}
//或
public int removeDuplicates(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int p = 0;
    int q = 1;
    while(q < nums.length){
        if(nums[p] != nums[q]){
            if(q - p > 1){
                nums[p + 1] = nums[q];
            }
            p++;
        }
        q++;
    }
    return p + 1;
}

2️⃣直接用Arrays.stream(nums).distinct().toArray()筛选不重复的元素，缺点是steam流不能重复使用，即使前面赋值了IntStream s，后面也只能使用一次。

import java.util.Arrays;
import java.util.stream.IntStream;
class Solution {
    public int removeDuplicates(int[] nums) {
        IntStream s= Arrays.stream(nums).distinct();
        System.arraycopy(s.toArray(),0,nums,0,Arrays.stream(nums).
               distinct().toArray().length);
        return Arrays.stream(nums).distinct().toArray().length;
    }
}

3️⃣压缩法删除相同元素
有序数组，可以把相同大小的数字压缩成同一个数字，而不同大小的数字存放在数组的不同位置。

public int removeDuplicates(int[] nums) {
    int length = nums.length;
    int j = 1;
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == nums[i + 1]) //如果两个相邻的元素相同
            length--;          //那么进行压缩，长度减少
        else
            nums[j++] = nums[i + 1]; //若两个相邻元素不同，那么对另外一个元素进行存储
    }
    return length;
}