删除有序数组中的重复项

## 1 题目

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

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

说明:

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

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

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

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

示例 1：

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

示例 2：

```txt
输入：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. [80. 删除有序数组中的重复项 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii)。
2. [83. 删除排序链表中的重复元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list)。
3. [82. 删除排序链表中的重复元素 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii)。

## 2 解题思路

### 2.1 快慢指针

#### 2.1 问题分析

1. **对于数组相关的算法问题，有一个通用的技巧：要尽量避免在中间删除元素，而是想办法把这个元素换到最后去。** 这样的话，最终待删除的元素都拖在数组尾部，一个一个 `pop` 掉就行了，每次操作的时间复杂度也就降低到 `O(1)` 了。
2. 按照这个思路，又可以衍生出解决类似需求的通用方式：双指针技巧。具体一点说，应该是快慢指针：
   1. 我们让慢指针 `slow` 走在后面，快指针 `fast` 走在前面探路，找到一个不重复的元素就告诉 `slow` 并让 `slow` 前进一步。
   2. 这样当 `fast` 指针遍历完整个数组 `nums` 后，`nums[0..slow]`**就是不重复元素，之后的所有元素都是重复元素。**

#### 2.2 参考代码

```java
/**
 * 26.删除有序数组中的重复项
 *
 * @param nums 数组
 * @return 删除后数组的新长度
 */
public static int removeDuplicates(int[] nums) {
    int slow = 0, fast = slow + 1;
    while (fast < nums.length) {
        if (nums[fast] != nums[fast - 1]) {
            slow++;
            nums[slow] = nums[fast];
        }
        fast++;
    }
    return slow + 1;
}
```

#### 2.3 扩展题目

##### 2.3.1 [删除有序数组中的重复项 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii)

###### 2.3.1.1 问题分析

1. 该题目也可以采用快慢指针的方法来解决，其中 $nums[0..slow]$**表示的不含重复次数超过最大限制的元素**，**之后的所有元素都是重复次数超过最大限制的元素**。
2. 整体的计算逻辑为**使用快慢指针对数组中的元素进行遍历**，其中**初始时 $slow = 0$**，$fast = slow + 1$，$count = 0$：
   1. **如果 $nums[slow] == nums[fast]$**：
      1. **将元素出现的次数计数器 $count$ 的值加 1**。
      2. **如果一个元素出现的次数达到了最大限制**，并且**后面还有元素**，则：
         1. **将 $nums[slow + 1]$ 赋值为 $nums[fast + 1]$**。
         2. **将 $fast$ 加 1**。
         3. **进行下一个循环**。
   2. 如果 $nums[slow] != nums[fast]$，则：
      1. **令元素出现的次数计数器 $count$ 为 0**。
   3. **将 $nums[slow + 1]$ 的值赋值为 $nums[fast]$**，**同时将两个指针依次向前移动一位**。

###### 2.3.1.2 参考代码

```java
/**
 * 80. 删除有序数组中的重复项 II
 * @param nums  有序数组
 * @return  删除重复项后有序数组的新长度
 */
public int removeDuplicates(int[] nums) {
    return process(nums, 2);
}

/**
 * 删除有序数组中的重复元素，使每个元素最多出现 k 次
 * @param nums  有序数组
 * @param k 每个元素最多出现的次数
 * @return  删除重复项后有序数组的新长度
 */
public int process(int[] nums, int k) {
    int m = nums.length;
    int slow = 0, fast = slow + 1, count = 0;
    //  用于解决类似于 [1,1,1] 的问题
    boolean except = false;

while (fast < m) {
        if (nums[slow] == nums[fast]) {
            count++;
            if (count >= k) {
                if (fast + 1 < m) {
                    //  如果 nums[slow] == nums[fast]，并且一个元素出现的次数达到了最大限制，并且后面还有元素，则
                    //      1. 将 nums[slow + 1] 赋值为 nums[fast + 1]
                    //      2. 将 fast 加 1
                    //      3. 进行下一个循环
                    nums[slow + 1] = nums[fast + 1];
                    fast++;
                    continue;
                } else {
                    except = true;
                }
            }
        } else {
            //  如果 nums[slow] != nums[fast]，则：
            //      1. 重置元素出现的次数计数器
            count = 0;
        }
        //  将 nums[slow + 1] 的值赋值为 nums[fast]
        nums[slow + 1] = nums[fast];
        //  将两个指针依次向前移动一位
        fast++;
        slow++;
    }

//  返回删除重复元素后数组的长度：
    //      1. 如果是类似于 [1,1,1] 的情况，则 返回 slow
    //      2. 否则，返回 slow + 1
    return except ? slow : slow + 1;
}
```

#### 2.3.2 [删除排序链表中的重复元素 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii)

##### 2.3.2.1 问题分析

1. 该题目也可以采用快慢指针来解决，其中$slow$为慢指针，$pre$为$slow$的前驱结点，$fast$为快指针，同时也为$slow$的后继节点，$same$ 表示当前操作的两个元素是否相等，$firstSame$ 表示头结点是否和其后继节点相同，主要为了解决 $[1, 1, *]$ 的特殊情况
2. 在一个循环中：
   1. 如果$slow$和$fast$节点的值相等：
      1. 将 $fast$ 节点后移，同时将 $slow$ 节点指向 $fast$ 节点，保证 $fast$ 节点始终是 $slow$ 节点的后继节点。
      2. 更新$same$的值为 `true`。
   2. 如果 $slow$ 和 $fast$ 节点的值不相等:
      1. 判断上一个操作中 $slow$ 和 $fast$ 的值是否相等:         1. 如果上一个操作中 $slow$ 和 $fast$ 的值相等，说明 $slow$ 节点也是相同节点的一部分，需要删除，因此将 $pre$ 指向 $slow$ 节点的下一个节点。
      2. 如果上一个操作中 $slow$ 和 $fast$ 的值不相等，则将 $pre$ 更新为 $slow$ 节点，后面再将 $slow$ 节点后移，使得 $pre$ 节点始终为 $slow$ 节点的前驱结点。
      3. 将 $slow$ 和 $fast$ 节点均后移。
      4. 更新 $same$ 的值为 `false`。
3. 如果$same$为 `true`，则将$pre$指向$slow$的下一个节点，以解决 $[*, 1, 1]$ 的特殊情况。
4. 最后如果首节点是相同节点的一部分，则将首节点删除，返回首节点的下一个节点，否则，返回首节点。

##### 2.3.2.2 参考代码

```java
/**
 * 82. 删除排序链表中的重复元素 II
 * @param head  排序链表的头结点
 * @return  删除重复元素后的排序链表
 */
public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {return head;}   //  如果头结点为空或者只有一个节点，则直接返回头结点
    ListNode pre = head, slow = head, fast = head.next; //  pre 为 slow 的前驱结点，fast 为 slow 的后继节点
    boolean same = false, firstSame = (slow.val == fast.val);   //  same 表示当前操作的两个元素是否相等，firstSame 表示头结点是否和其后继节点相同，主要为了解决 [1, 1, *] 的特殊情况
    while (fast != null) {
        /**
         * 如果 slow 和 fast 节点的值相等:
         *  1. 将 fast 节点后移，同时将 slow 节点指向 fast 节点，保证 fast 节点始终是 slow 节点的后继节点
         *  2. 更新 same 的值为 true
         */
        if (slow.val == fast.val) {
            fast = fast.next;
            slow.next = fast;
            same = true;
        } else {
            /**
             * 如果 slow 和 fast 节点的值不相等:
             *  1. 判断上一个操作中 slow 和 fast 的值是否相等:
             *      1.1 如果上一个操作中 slow 和 fast 的值相等，说明 slow 节点也是相同节点的一部分，需要删除，因此将 pre 指向 slow 节点的下一个节点
             *      1.2 如果上一个操作中 slow 和 fast 的值不相等，则将 pre 更新为 slow 节点，后面再将 slow 节点后移，使得 pre 节点始终为 slow 节点的前驱结点
             *  2. 将 slow 和 fast 节点均后移
             *  3. 更新 same 的值为 false
             */
            if (same) {pre.next = slow.next;}
            else {pre = slow;}
            slow = slow.next;
            fast = fast.next;
            same = false;
        }
    }
    if (same) {pre.next = slow.next;}   //  解决 [*, 1, 1] 的特殊情况
    return firstSame ? head.next : head;    //  如果首节点是相同节点的一部分，则将首节点删除，返回首节点的下一个节点，否则，返回首节点
}
```

## 参考文献

1. [26. 删除有序数组中的重复项](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array)。
2. [80. 删除有序数组中的重复项 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii)。
3. [83. 删除排序链表中的重复元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list)。
4. [82. 删除排序链表中的重复元素 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii)。
5. [如何去除有序数组的重复元素](https://labuladong.gitbook.io/algo/mu-lu-ye-3/mu-lu-ye-2/yuan-di-xiu-gai-shu-zu)。