一、题目描述
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [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]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。提示：
0 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums已按 升序 排列
二、思路分析
看到这个题，我们会发现这题不难，先说最容易想到一种解法，就是最简单粗暴地移动，每次发现重复元素，就把后面的元素往前移动。最后得到想要的结果。
但是这地方有一个问题，就是时间复杂度比较高，数组的移动不像链表，需要把后面的每个元素都重新复制，这时候的时间复杂度就能到达O(n^2)
那么我们是不是可以想办法，降低一些时间复杂度呢？
这个也是可以，假设我们再新建一个数组，遍历原来的nums数组，每次发现非重复的元素，就添加到新数组中，重复元素就跳过。这个有一点需要注意，最后的时候，需要把新建数组的元素赋值到原来的nums数组中。
public class Solution {
public int removeDuplicates(int[] nums) {
// 如果是空数组，直接返回
if (nums.length == 0) {
return 0;
}
// 新建一个数组，保存非重复元素
int[] temp = new int[nums.length];
temp[0] = nums[0];
// 新建变量，记录新建数组冲需要添加元素的位置
int k = 1;
// 查找非重复的元素，添加到新的数组中
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]) {
temp[k++] = nums[i];
}
}
// 新数组的元素写到原数组的指定位置上
for (int i = 1; i < k; i++) {
nums[i] = temp[i];
}
return k;
}
}复杂度分析
- 时间复杂度：
O(n) - 空间复杂度：
O(n)
虽然这种解法可以解答题目，但是题目中说到不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
我们通过上面两种解法来分析一下怎么做到原地修改，第一种方法就是简单粗暴的移动后面的所有的元素，有一些重复元素也被移动了，非重复元素移动的位置不对，需要移动多次，花费多余的时间。第二种元素利用了新建的数组，使用了新空间，不是原地修改。
那么我们是不是可以先找到一个重复的元素，当做新建的空间，然后再找到一个不重复的元素，每次只交换这两个数据，一次遍历完nums数组，就可以把所有非重复的元素都放到前面的位置上了。
示例代码
public class Solution {
public int removeDuplicates(int[] nums) {
// 定义一个变量，记录重复元素的位置，默认为-1
int a = -1;
// 查找第一个重复元素的位置
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
a = i;
break;
}
}
// 如果没有找到重复元素，直接返回结果
if (a == -1) {
return nums.length;
}
// 遍历元素，每次把后面不重复元素跟前面重复的元素交换位置
for (int i = a + 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]) {
nums[a++] = nums[i];
}
}
// a的值，正好是非重复元素数组的长度
return a;
}
}复杂度分析
- 时间复杂度：
O(n) - 空间复杂度：
O(1)
三、总结
双指针这种操作不仅适用于链表，有时候在数组上也可以进行操作。涉及到数组元素的操作时，可以考虑是否把数组元素一步移动到指定的位置，减少不必要的次数。此外就是尽量保证是原地操作。
