一、问题
给定一个排序数组，在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，在原地修改输入数组并在使用 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();
System.out.println(testDemo.removeDuplicates(nums));
}
1️⃣双指针法
数组是有序的，重复的元素一定会相邻。要求删除重复元素，实际上就是将不重复的元素移到数组的左侧。可以放置两个指针 p 和 q，其中 p 是慢指针，而 q 是快指针。算法流程如下：
- 比较 p 和 q 位置的元素是否相等。
- 如果相等，q 后移一位。如果不相等，将 q 位置的元素复制到 p+1 位置上，p 后移一位，q 后移一位。
- 重复上述过程，直到 q 等于数组长度。返回 p + 1，即为新数组长度。
- 说明：如图此时数组中没有重复元素，每次比较 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()筛选不重复的元素，缺点是 stream 不能重复使用，即使前面赋值了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;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) //如果两个相邻的元素相同
length--; //那么进行压缩，长度减少
}
return length;
}
