26. 删除有序数组中的重复项
给你一个 升序排列 的数组 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 。不需要考虑数组中超出新长度后面的元素。
思路分析
接下来我们以数组{1, 1, 2, 3, 3, 4}为例，看下如何删除排序数组中的重复项，使得每个元素只出现一次。
首先，定义慢指针slow，指向数组中的第一个元素。
我们规定在区间[0,slow]中的元素都是排序数组中只出现一次的元素。慢指针slow的初始值为0，表示区间[0,0]中的元素，即数组中的第一个元素是只出现一次的元素。
接着定义快指针fast，其所指向的元素为当前在考察的元素。因为数组是排好序的，因此数组中的第一个元素是一定存在于返回数组中的，所以从第二个元素开始考察，即快指针fast的初始值为1，如下图。
当前快指针fast=1所指向的元素值为1，与慢指针slow所指向的元素值相同。
因此，快指针fast向后移动一位，继续考察下一个元素，如下图。这时，快指针fast=2所指向的元素值为2与慢指针slow所指向的元素值1不相同，应放到区间[0,slow]中，也就是说快指针停止的条件是当前考察的元素值与区间[0,slow]末尾元素值不等。
因为区间[0,slow]是左闭右闭区间，其中的元素是只出现一次的元素。因此，慢指针slow需要向后移动一个位置来扩大区间。然后，将快指针fast所指向的元素值赋予慢指针所指向的元素位置。
此时，区间[0,slow]，即[0,1]中包含的元素1，2都是排序数组删除重复项之后，只出现一次的元素。
对于排序数组中剩余未考察的元素3，3，4重复上述步骤即可将重复项删除。
代码实现
package com.codernav.demo.leetcode.array.removeelement;
import java.util.Arrays;
/**
* 26. 删除有序数组中的重复项
* 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
* 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
* 将最终结果插入 nums 的前 k 个位置后返回 k 。
* 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
* 原文地址：https://www.codernav.com/2886.html
* 更多算法详解：https://www.codernav.com
*/
public class Q_26 {
public static void main(String[] args) {
int[] nums = new int[]{0, 1, 1, 1, 2, 2, 3, 3, 4};
System.out.println(f(nums));
int[] nums1 = new int[]{0, 1, 1, 1, 2, 2, 3, 3, 4};
System.out.println(removeDuplicates(nums1));
}
private static int f(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0;
for (int fast = 0; fast < nums.length - 1; fast++) {
System.out.println("slow:" + slow + ", fast:" + fast + ", nums:" + Arrays.toString(nums));
if (nums[fast] != nums[fast + 1]) {
slow++;
nums[slow] = nums[fast + 1];
}
}
return slow + 1;
}
public static int removeDuplicates(int[] nums) {
// 区间[0,slow]中的元素都是排序数组中只出现一次的元素
int slow = 0;
// 快指针fast的初始值为1，因为数组是排好序的
// 因此数组中的第一个元素是一定存在于返回数组中的。
for(int fast = 1; fast < nums.length; fast++) {
// 当前考察的元素nums[fast]和nums[slow]不相等时
// 说明nums[fast]是需要放入区间[0,slow]中的
if (nums[fast] != nums[slow]) {
// slow++是因为区间[0,slow]是左闭右闭的
// 因此，在slow加1之后，在将nums[fast]的值赋予nums[slow]
slow++;
nums[slow] = nums[fast];
}
}
// j指向的是新数组中末尾的元素，即新数组最后的索引
// 而索引从0开始，题目要求返回新数组的长度，因此返回slow+1
return slow + 1;
}
}
我的分析：
1、定义slow和fast两个指针。慢区间[0,slow]中的元素都是排序数组中只出现一次的元素。
2、快指针fast的初始值为1，因为数组是排好序的, 因此数组中的第一个元素是一定存在于返回数组中的。
3、循环遍历[1,fast],当前考察的元素nums[fast]和nums[slow]不相等时,说明nums[fast]是需要放入区间[0,slow]中的
4、slow++是因为区间[0,slow]是左闭右闭的，因此，在slow加1之后，在将nums[fast]的值赋予nums[slow]
5、索引从0开始，题目要求返回新数组的长度，因此返回slow+1
注意：
当nums[fast] != nums[slow]时，slow++和nums[slow] = nums[fast];哪个在前面？
在“27. 移除元素”那道题中，我们是先赋值，再++，为什么这道题是先++再赋值呢？因为“27. 移除元素”题解中，slow和fast都是从0开始的，而本题中slow比fast慢了一步，所以要先++，保持下标一致。
相关文章
