题目

力扣题目链接

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

提示：

  • 0 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按升序排列

说明:
为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

  1. // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
  2. int len = removeDuplicates(nums);
  4. // 在函数里修改输入数组对于调用者是可见的。
  5. // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
  6. for (int i = 0; i < len; i++) {
  7.     print(nums[i]);
  8. }

示例1：

  1. 输入：nums = [1,1,2]
  2. 输出：2, nums = [1,2]
  3. 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。
  4. 不需要考虑数组中超出新长度后面的元素。

示例2：

  1. 输入：nums = [0,0,1,1,1,2,2,3,3,4]
  2. 输出：5, nums = [0,1,2,3,4]
  3. 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。
  4. 不需要考虑数组中超出新长度后面的元素。

思路

在做这道题前，先把 27. 移除元素 做了。

同样的，我们可以利用双指针法来解决这道问题。

经过上一题，我们知道了 双指针法可以避免 for 循环嵌套，因此可以将时间复杂度 O(n^2) 的解法优化至 O(n) 。

答案

Java

双指针法

  1. # 与 27. 移除元素 相似的写法
  2. class Solution {
  3.     public int removeDuplicates(int[] nums) {
  4.         // 快慢双指针
  5.         int slowIndex = 0, fastIndex = 0;
  7.         // 快指针遍历数组
  8.         for (; fastIndex < nums.length; fastIndex++) {
  9.             // 如果当前快指针指向的值不等于慢指针指向的值
  10.             if (nums[fastIndex] != nums[slowIndex]) {
  11.                 // 先将慢指针右移, 再使用快指针指向的值覆盖慢指针指向的值
  12.                 nums[++slowIndex] = nums[fastIndex];
  13.             }
  14.         }
  16.         return slowIndex + 1;
  17.     }
  18. }

REF

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/dai-ma-sui-xiang-lu-26-shan-chu-you-xu-s-hsc9/