# Remove Duplicates from Sorted Array

###### tags: `Easy`
> [name=出題者 : 曾致銘]

## Problem
給定一個整數 `n` 以及長度為 `n` 且以**升序排列**的整數陣列 `nums`，要求[原地](https://zh.wikipedia.org/zh-tw/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95)刪除重複的元素並使得每一個整數只出現**一次**。元素的**相對順序**應保持**不變**。

你不一定要選擇「刪除」重複的元素，因為在 C++ 中，你是無法原地刪除標準陣列中的元素的，因此你可以選擇只保持 `nums` 的**前段部分**符合要求。具體而言，我們令刪除完重複項的陣列元素應該有 `k` 個，那麼你至少要使得 `nums` 的前 `k` 個元素符合題目要求，而對於其餘的元素皆沒有任何要求。

在刪除完重複項後，印出處理後的 `nums` (可包含後段的元素)，再印出 `k` (預期陣列的長度)。

你**不能**創建任何額外的陣列。你必須[原地](https://zh.wikipedia.org/zh-tw/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95)**修改輸入陣列**並使得空間複雜度為 $O(1)$。

**預期檢查方法：**
為了方便理解，這裡列舉一個你的演算法預期所能通過的檢查：

int outputK; // 此為你的演算法所印出的 k 值
int expectedK; // 此為預期的 k 值
int outputNums[]; // 此為你的演算法輸出的陣列
int expectedNums[]; // 此為預期的輸出陣列

assert(expectedK == outputK);

for (int i = 0; i < expectedK; i++) {
    assert(outputNums[i] == expectedNums[i]);
}

你的演算法是完善的若且唯若所有的 assertion 都被通過。

*註: 你不一定要使用標準陣列來解題，你也可以使用其他有陣列功能的物件，如 `vector<>`。且如果可以，盡量使用 `vector<>` 而非標準陣列來解題。*
*註: 你輸出的陣列 `nums` 與預期長度 `k` 之間應該空兩格以區分彼此。*
*註: 你必須將所有輸入值存入一個陣列中，再進行處理。你不能在所有輸入儲存完畢之前處理。提供參考程式碼如下：*

int nums[n];

for (auto& num : nums) {
    cin >> num;
}

// 從此處開始撰寫你的演算法

### Examples
範例 1：

輸入: 3 1 1 2
輸出: 1 2 _  2 或 1 2  2
解釋: 你的演算法應該輸出 k = 2, 且 nums 的前兩項應為 1, 2。對於第三項的元素則沒有要求 (故用底線表示)。

範例 2：

輸入: 10 0 0 1 1 1 2 2 3 3 4
輸出: 0 1 2 3 4 _ _ _ _ _  5 或 0 1 2 3 4  5
解釋: 你的演算法應該輸出 k = 5, 且 nums 的前五項應為 0, 1, 2, 3, 4。對於第六項以後的元素則沒有要求 (故用底線表示)。

### Constraints
- $1 \le$ `nums.size()` $\le 3 \cdot 10^4$
- $-100 \le$ `nums[i]` $\le 100$
- `nums` 依照**升序排列**。

### Hints
:::spoiler Hint 1
在本題目中，最關鍵的地方在於輸入的陣列是有序的。那麼對於「重複的元素」而言，他們在輸入的陣列中的位置會有什麼特點？請從下圖來找尋答案。倘若我們知道了某個元素的位置，我們是否能知道和它重複的元素的位置呢？
:::

:::spoiler Hint 2
我們需要原地修改輸入陣列且最後的陣列長度必然會小於等於輸入陣列長度。因此，本題很適合使用**雙指針 (two-pointer)** 算法來處理，滿足其中一個指針負責從頭遍歷整個陣列，且同時另一個指針負責不重複的元素紀錄。
:::

:::spoiler Hint 3
實際上，當你遇到一個元素時，你只需要**跳過**重複的元素並移動至下一個相異元素即可。
:::

### Extra Challenge
請試著在不減少輸入陣列的長度下完成此題 (只可修改，不可刪除)。

## Solution
如果我們可以用額外空間來解題，那麼將會變得輕鬆許多。
我們可以創建一個表格 (Map) 來將**不重複的數字**存入鍵 (Key)，和將其**出現次數**存入值 (Value)。
在存完資料後，我們便能得到所有不重複數字的組合。
接著，就可以遍歷該表格並將所有鍵寫入輸入陣列。
然而，在不使用額外空間的情況下，我們就需要用另一種方式來達成。

:::spoiler Description
### Approach 1: 雙指針 (two-pointer) 算法

#### 思路
在解題之前，讓我們仔細的觀察題目的要求。

> 輸入陣列被**確保**一定是以**升序排列**的。

令 `k` 為輸入陣列中不重複元素的個數。

> 對於前 `k` 項以外的元素皆沒有任何要求。

通過這些條件，我們可以觀察到：

- 因為陣列是升序排列的，所以所有重複的元素必然相連。
- 我們需要修改前 `k` 項元素並印出 `k`。

透過這些想法，讓我們思考如何解決此題：

- 題目要求我們要將不重複元素填入前 `k` 項。
- 且同時必須原地修改且不得使用額外空間。
- 為了做到這兩點，我們可以使用**雙指針**算法。
- 當其中一個指針在遍歷陣列時，另一個指針紀錄並寫入不重複的元素。

> 我們讓**第一個指針**負責記錄不重複項，且同時**第二個指針**遍歷輸入陣列讓第一個指針使用。

- 重複以上步驟直到**第二個指針**遍歷完成。

#### 算法
通過分析上述想法，我們可以列出以下具體算法：

- 創建兩指針 `insertIndex` , `i` 並使得 `(insertIndex, i) = 1`

> `insertIndex` 和 `i` 分別表示上述的第一指針與第二指針。

- 檢查前一個元素是否和當前元素相同

> 「前一個」元素表示第 `i-1` 項元素。(例：`nums[i-1]` )

- 倘若不一致，那麼令 `nums[insertIndex] = nums[i]` 並將 `insertIndex` 增加 1。
- 將 `i` 增加 1 後，重複這些步驟直到遍歷結束。

> 註：當遍歷結束後，`insertIndex` 所停留的位置剛好可以代表不重複元素的個數。


// 以下省略 cin, cout，僅呈現演算法部分
int insertIndex = 1;

for (int i = 1; i < nums.size(); i++) {
    // 當元素重複時，直接跳過
    if (nums[i - 1] != nums[i]) {
        // 儲存相異元素並將 insertIndex 增加 1
        nums[insertIndex] = nums[i];
        insertIndex++;
    }
}

#### 複雜度分析
- 時間複雜度: $O(n)$，因為我們只用了兩個指針，且都只會至多遍歷輸入陣列一次。
- 空間複雜度: $O(1)$，因為我們沒有使用額外空間。

### 完整解答

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int nums[n];
    
    for (auto& num : nums) {
        cin >> num;
    }
    
    int insertIndex = 1;
    cout << nums[0] << " ";
    
    for (int i = 1; i < n; i++) {
        if (nums[i - 1] != nums[i]) {
            nums[insertIndex] = nums[i];
            insertIndex++;
            cout << nums[i] << " ";
        }
    }
    
    cout << " " << insertIndex << endl;
}

:::

## Reference
本題目所有內容均為翻譯 LeetCode 內容，且圖片，解答均為搬運。
https://leetcode.com/problems/remove-duplicates-from-sorted-array/