# 26. Remove Duplicates from Sorted Array

### Leetcode

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

### 題目

Given an integer array `nums` sorted in **non-decreasing order**, remove the duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) such that each unique element appears only **once**. 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,2]
</strong><strong>Output: 2, nums = [1,2,_]
</strong><strong>Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 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,2,2,3,3,4]
</strong><strong>Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
</strong><strong>Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 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>

* **方法一 - Two pointer**

仿照第 27. 題用雙指針的解法，先固定左指針，右指針從左指針往後找到 **大於左指針數值的元素**，再與左指針後的下一個元素進行交換

```javascript
var removeDuplicates = function (nums) {
    let output = 1;

    let i = 0;
    let j = 1;

    const swap = (i, j) => {
        const temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        output++;
    }

    while (i < nums.length - 1) {
        let value = nums[i];

        while (j < nums.length) {
            // 右指針往後找到大於 i 所在位置的元素
            if (nums[j] <= value) {
                j++;
            } else {
                // 交換元素
                swap(i + 1, j);
                break;
            }
        }
        // 左指針往後
        i++;
    }

    return output;
};
```

Runtime: 62 ms Beats 68.37% of users with JavaScript

Memory: 51.83 MB Beats 75.07% of users with JavaScript

* **方法二**

利用 splice 方法，當遇到前一個元素重複時直接移除掉

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

    return nums.length;
};
```

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

由於矩陣已經排序過了，所以我們可以使用快慢指針的方式來將 **非重複的值** 與前面重複的值進行交換

範例：

```
nums = [0,0,1,1,1,2,2,3,3,4]
```

首先一開始固定 **慢指針(slow)** 在第一個元素的位置，**快指針(fast)** 在第二個元素的位置，快指針會不斷地往後移動，當遇到慢指針所在的元素與快指針所在的元素不同時，就可以將慢指針的下一個元素與快指針的元素交換，這樣就可以把快指針所在的 **非重複的值** 依序往前交換移動

```javascript
var removeDuplicates = function (nums) {
    let slow = 0;

    for (let fast = 1; fast < nums.length; fast++) {
        if (nums[slow] !== nums[fast]) {
            slow++;
            nums[slow] = nums[fast];
        };
    }

    return slow + 1;
};
```

Runtime: 67 ms Beats 47.16% of users with JavaScript

Memory: 52.41 MB Beats 36.69% of users with JavaScript

### 測資

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

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

### 參考資料

{% embed url="<https://ithelp.ithome.com.tw/articles/10270237>" %}
