# 80. Remove Duplicates from Sorted Array II

### Leetcode

<https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/>

### 題目

Given an integer array `nums` sorted in **non-decreasing order**, remove some duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) such that each unique element appears **at most twice**. The **relative order** of the elements should be kept the **same**.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the **first part** of the array `nums`. More formally, if there are `k` elements after removing the duplicates, then the first `k` elements of `nums` should hold the final result. It does not matter what you leave beyond the first `k` elements.

Return `k` *after placing the final result in the first* `k` *slots of* `nums`.

Do **not** allocate extra space for another array. You must do this by **modifying the input array** [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) with O(1) extra memory.

**Custom Judge:**

The judge will test your solution with the following code:

```
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}
```

If all assertions pass, then your solution will be **accepted**.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,1,1,2,2,3]
</strong><strong>Output: 5, nums = [1,1,2,2,3,_]
</strong><strong>Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
</strong>It does not matter what you leave beyond the returned k (hence they are underscores).
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [0,0,1,1,1,1,2,3,3]
</strong><strong>Output: 7, nums = [0,0,1,1,2,3,3,_,_]
</strong><strong>Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
</strong>It does not matter what you leave beyond the returned k (hence they are underscores).
</code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

**利用矩陣的 splice 方法**

```javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  let target = nums[0];
  let count = 0;
  
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) {
      count++;
      if (count > 2) {
        nums.splice(i, 1);
        i--;
      }
    } else {
      target = nums[i];
      count = 1;
    }
  }

  return nums.length;
};
```

* **方法二 - 快慢指針**

慢指針指向重複兩個數字的後面那個數字，快指針遍歷所有矩陣

```javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  const MAX = 2;
  let count = 1;
  let slow = 0;

  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[slow] === nums[fast]) {
      if (count < MAX) {
        count++;
        // 需要把後面的 fast 移到前面 slow 的後面
        // ex. 1, 1, 2(slow), 1, 2(fast)
        // =>  1, 1, 2, 2, 1
        slow++;
        nums[slow] = nums[fast];
      }
    } else {
      slow++;
      nums[slow] = nums[fast];
      count = 1;
    }
  }

  return slow + 1;
};
```

Runtime: 63 ms Beats 48.93% of users with JavaScript

Memory: 51.42 MB Beats 61.39% of users with JavaScript

* **方法三 - 快慢指針進化版**

前一個解法我們用 `count` 來記錄重複數值的數量是否有超過 2，但其實可以連 `count` 都不需要，原因是可以拿快指針去與慢指針的前一個元素進行比較

例如：

```
快指針所在元素跟慢指針的前一個元素比較 (不相等)

1 1 2
  s f
  
1 2 2
  s f 
```

由於題目給的矩陣是由小到大排序過的，所以當 **快指針所在的元素** 與 **慢指針的前一個元素** 不相等時，這個 **快指針所在的元素** 一定不會是重複的，這時就可以把快指針所在的元素添加進矩陣

而如果 **快指針所在的元素** 與 **慢指針的前一個元素** 相等時，代表 **快指針所在的元素** 已經重複了，所以需要將快指針往後移動

```
快指針跟慢指針的前一個數值比較

相等的狀況 => 已經重複 => 快指針需要往後移動
1 1 1 1 1 2 2 3
  s   f
  
不相等的狀況 => 不會重複 => 將快指針所在元素移到慢指針的後面
1 1 1 2 2 3 3 3
  s   f
```

```javascript
var removeDuplicates = function (nums) {
    if (nums.length === 1) return 1;

    const MAX = 2;
    let slow = 1;

    for (let fast = 2; fast < nums.length; fast++) {
        // 快指針跟慢指針的前一個數值比較
        if (nums[fast] !== nums[slow - MAX + 1]) {
            // 如果數值不相等的話，代表快指針所在的元素一定不是重複的，將這個元素添加進去
            slow++;
            nums[slow] = nums[fast];
        }
    }

    return slow + 1;
};
```

### 參考資料

{% embed url="<https://leetcode.wang/leetCode-80-Remove-Duplicates-from-Sorted-ArrayII.html>" %}

### 測資

```javascript
let nums = [1,1,1,2,2,3];
nums = [0,0,1,1,1,1,2,3,3];

const result = removeDuplicates(nums)
console.log(nums, result);
```
