1?題目描述

2?題目解讀

????????對于有序數(shù)組nums，要求在不使用額外數(shù)組空間的條件下，刪除數(shù)組nums中重復(fù)出現(xiàn)的元素，使得nums中出現(xiàn)次數(shù)超過兩次的元素只出現(xiàn)兩次。返回刪除后數(shù)組的新長度。

3?解法一：雙指針

????????雙指針法可以很好地解決此題。

3.1?解題思路

????????設(shè)置雙指針，從數(shù)組nums的第3個元素開始比較，直到nums的最后一個元素。

3.2?設(shè)計代碼

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if (n <= 2) {return n;}int slow = 2, fast = 2;while (fast < n) {if (nums[slow - 2] != nums[fast]) {nums[slow] = nums[fast];++slow;}++fast;}return slow;}
};
int main() {int x[] = { 1,1,1,2,2,3 };vector<int> nums;for (int i = 0; i < 6; i++){nums.push_back(x[i]);}Solution S;int ans = S.removeDuplicates(nums);cout << ans << endl;return 0;
}

3.3?復(fù)雜度分析

• 時間復(fù)雜度：。while循環(huán)遍歷了一遍數(shù)組元素。
• 空間復(fù)雜度：。沒有使用額外數(shù)組空間。

3.4?提交結(jié)果

4?解法二：前移法

????????前移法是由雙指針法擴展出來的一種方法，與雙指針法有著相似的思想。

4.1?解題思路

????????設(shè)置指針right，從數(shù)組nums的第3個元素開始遍歷，使用變量k記錄需要移除的元素的個數(shù)，將需要移動的元素前移k個位置。

4.2?設(shè)計代碼

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if (n <= 2) {return n;}// k累計刪除的元素個數(shù)int fast = 2, k = 0;while (fast < n) {if (nums[fast - k - 2] != nums[fast]) {nums[fast - k] = nums[fast];}else {++k;}++fast;}return fast - k;}
};
int main() {int x[] = { 1,1,1,2,2,3 };vector<int> nums;for (int i = 0; i < 6; i++){nums.push_back(x[i]);}Solution S;int ans = S.removeDuplicates(nums);cout << ans << endl;return 0;
}

4.3?復(fù)雜度分析

• 時間復(fù)雜度：。while循環(huán)遍歷了一遍數(shù)組nums的元素。
• 空間復(fù)雜度：。沒有使用額外數(shù)組空間。

4.4?提交結(jié)果

5?解題心得

• 讓有序數(shù)組nums中重復(fù)出現(xiàn)的元素只出現(xiàn)兩次，是讓其只出現(xiàn)一次的變體題目，難度更大。
• 雙指針法與前移法之間，可以相互轉(zhuǎn)換。
• 雙指針法中，left指針用于放置新元素。