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;
}
這個解法的思路很簡單:
- 計算跟「當前元素」值相同的元素個數
- 跳過跟「當前元素」重複的值,把後面的元素往前移動到新的位置
雖然這個解法可以通過 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;
}
這個解法的思路是這樣:
i
變數為當前被比較的值的索引值- 比對
i
之後的元素,跳過所有重複值 - 一旦找到非重複值,我們就把位於
j
的非重複值移動至i+1
的位置 - 因為在第三步驟
i
已經加一,代表我們現在比對的元素變成第三步驟的值 - 重複上述步驟
由此可知,i
最後的值會等於剔除掉重複元素後的最後一個元素的索引值,但因為陣列索引值都是以 0 開始的關係,最後 return
的時候要加一才會等於陣列的新長度。
看解答可以發現,官方給的解法比我想出來的解法簡潔許多,而且也避免了很多不必要的運算。