題目:
給一個排序過的陣列 nums
,請你「原地」移除重複的元素,使每個元素只出現一次,並回傳移除後的新長度。不要使用額外的空間,必須在原地修改來源的陣列。
範例:
輸入:
nums = [0,0,1,1,1,2,2,3,3,4]
輸出:
長度 = 5, nums = [0,1,2,3,4]
函式應回傳新長度 5,並將前五個元素修改為 [0, 1, 2, 3, 4]
。你不需要考慮陣列中超出新長度之後的元素。
使用快慢指標,i 慢指標為確定的不重複結果,j 快指標則是找跟 i 不同的元素,找到後並覆蓋到i+1的位置,遍歷完以後 i+1 就是最後的新長度。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int i = 0;
for (int j = 1; j < nums.size(); j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i+1;
}
};
時間複雜度:O(n)
空間複雜度:O(1)
參考:
#26. Remove Duplicates from Sorted Array