[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 的時候要加一才會等於陣列的新長度。

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

comments powered by Disqus
分享至 Facebook 分享至 Google +