[LeetCode 解題筆記] Remove Duplicates from Sorted Array

LeetCode 原問題網址：26. Remove Duplicates from Sorted Array

題目敘述

input 會給你一個排序過後的陣列，實作一個 function 把重複的值剔除(in-place 移除，不分配額外的空間)，使每個元素都只出現一次，function 回傳陣列的新長度。

解法

我第一個想到的解法如下：

int removeDuplicates(int* nums, int numsSize) {
    int size = numsSize;

    for (int i=0; i<size; i++) {
        int duplicatesCount = 0;
        for (int j=i+1; j<size; j++) {
            if (nums[i] == nums[j]) {
                duplicatesCount++;
            } else {
                break;
            }
        }

        // move elements after duplicates into new position
        int newIndex = i+1;
        for (int k=i+duplicatesCount+1; k<size; k++) {
            nums[newIndex++] = nums[k];
        }
        size -= duplicatesCount;
    }
    return size;
}

這個解法的思路很簡單：

1. 計算跟「當前元素」值相同的元素個數
2. 跳過跟「當前元素」重複的值，把後面的元素往前移動到新的位置

雖然這個解法可以通過 LeetCode 測試，但有點過於直覺，效能也不太優異。

讓我們看看 LeetCode 官方提出的解法：

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    int i = 0;
    for (int j = 1; j < numsSize; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

這個解法的思路是這樣：

1. i 變數為當前被比較的值的索引值
2. 比對 i 之後的元素，跳過所有重複值
3. 一旦找到非重複值，我們就把位於 j 的非重複值移動至 i+1 的位置
4. 因為在第三步驟 i 已經加一，代表我們現在比對的元素變成第三步驟的值
5. 重複上述步驟

由此可知，i 最後的值會等於剔除掉重複元素後的最後一個元素的索引值，但因為陣列索引值都是以 0 開始的關係，最後 return 的時候要加一才會等於陣列的新長度。

看解答可以發現，官方給的解法比我想出來的解法簡潔許多，而且也避免了很多不必要的運算。