:-: 1.1 删除排序数组中的重复项 * * * * * **题干：** 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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。 你不需要考虑数组中超出新长度后面的元素。 ~~~ 说明: 为什么返回数值是整数，但输出的答案是数组呢?请注意，输入数组是以“**引用**”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下: ~~~ // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); } ~~~ **题目分析：** 首先看题，题目的要求并不是删除元素的重复项，而是把排除元素重复项后的不重复的元素在有序排在数组前几个位置，接着有序不用考虑，题目给的数组本就有序（这个我们不能破坏，我们不给自己找麻烦），我们剩下的就要思考如何把不重复的元素排在数组前几个位置。 **新手有可能遇到的解题思路陷阱：** 新手嘛，首先的思路肯定考虑的是暴力破解的方法思路：我们首先要“去除”重复元素，这个元素怎么去除呢？很容易的想法就是把重复值替换为一个数组不可能出现的的值，然后把不重复的元素在有序排在数组前几个位置，怎么排？我们可以想到只要从头到尾遍历，只要检测到这个不可能的值，就和它后面第一个正常值交换就可以了，然后返回正常值的个数就可以了。 但是，说到但是了，这样的思路的重要点就在于这个“数组中不可能出现的值”，这个你怎么找？就算你LeetCode运行通过了，这也不代表你这这个算法没有问题！！！ **解题思路分析以及代码实现：** 第一种思路：首位可替换，重复就去除，长度要减一，然后重复检（后面的值代替前面的已经被检测出重复的值，有前移，下次检测的长度就减一，然后重新再按上次的检测位置重新检测）。 第一种思路代码： ~~~ public static int removeDuplicates(int[] nums) { if(nums.length == 0) return 0; int len= nums.length; for(int i=1;i<len;) { if(nums[i]==nums[i-1]) { for(int j=i;j<len;j++) nums[j-1]=nums[j]; len--; } else { i++; } } return len; } ~~~ **复杂度分析** 时间复杂度：O(n^2)。 空间复杂度：O(1)。 第二种思路：首位不可替换，重复值不处理，外联替换位置（首位我们不在改变它，它就是第一个不重复的值，然后我们需要一个变量来确定我们重复值被不重复的值替换的位置，且重复的值不做处理，直接忽略过）。 第二种思路代码： ~~~ public static int removeDuplicates(int[] nums) { //第一种 if(nums.length == 0) return 0; int count = 1; for(int i=1;i<nums.length;i++){ if(nums[i-1] != nums[i]){ nums[count++] = nums[i]; } } return count; //第二种实现方式 /*if(nums.length == 0) return 0; int index=0; for(int i =1 ; i < nums.length ; i++){ if ( nums[i] != nums[index]){ index ++; nums[index] = nums[i]; } } return ++index;*/ } ~~~ **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(1)。 **官方解法：** 方法：双指针法 数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要 nums[i]=nums[j]，我们就增加 j 以跳过重复项。 当我们遇到 nums[j]≠nums[i] 时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]）的值复制到 nums[i + 1]。然后递增 i，接着我们将再次重复相同的过程，直到 j 到达数组的末尾为止。 ~~~ public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int i = 0; for (int j = 1; j < nums.length; j++) { if (nums[j] != nums[i]) { i++; nums[i] = nums[j]; } } return i + 1; } ~~~ **复杂度分析** 时间复杂度：O(n)， 假设数组的长度是 n，那么 i 和 j 分别最多遍历 n 步。 空间复杂度：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**