LeetCode’s Note: (26) Remove Duplicates from Sorted Array

Question:

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Explanation:

從題目的描述與範例，可以得知：給定一個已經排序過後的陣列，必須以 in-place 的方式將陣列中重複出現的數字刪除，最後回傳陣列的長度。

Brute Force:

看完題目後，第一個所想到的解決方法勢必是檢查陣列中的每一個元素，然後將重複出現的元素進行刪除，最後再回傳這個陣列的長度。

Efficient Way:

實際上並不需要真的將陣列中重複出現的數字刪除，而是將「每一種」數字擺放到陣列中正確的位置即可。

舉例來說：給定一個已經排序過的陣列（如上圖所示）。

i 表示目前檢查的元素；j 表示「下一種」數字所應該在的位置。因為第一種數字是 0 已經出現在正確的位置（index = 0），所以「下一種」數字應該出現的正確位置必須從為 1 開始。

當 i 繼續往前檢查（index = 2）時，發現到「新一種」的數字（1），則必須將此「新一種」數字放置到正確的位置（index = j）。

將「新一種」數字放置到正確的位置（index = j）後，j 必須再往前移動一個位置，代表下一個新一種位置應該存放的位置。

最後，當 i 檢查完所有的元素之後，j 即表示修改後的陣列的長度。

Implement（Golang）:

雖然在 Matters 上似乎比較少是程式（編程）類別的文章，導致讀者應該也很少，但還是希望可以在這裡分享自己的所學，並透過簡單的文字與解釋呈現出來。希望本篇文章解釋得夠詳細與簡單，能夠給予卡在這個題目的你實質的幫助～感謝你的閱讀！