力扣80、删除有序数组中的重复项Ⅱ（中等）

1 题目描述

图1 题目描述

2 题目解读

        对于有序数组nums，要求在不使用额外数组空间的条件下，删除数组nums中重复出现的元素，使得nums中出现次数超过两次的元素只出现两次。返回删除后数组的新长度。

3 解法一：双指针

        双指针法可以很好地解决此题。

3.1 解题思路

        设置双指针，从数组nums的第3个元素开始比较，直到nums的最后一个元素。

3.2 设计代码

#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 复杂度分析

• 时间复杂度：。while循环遍历了一遍数组元素。
• 空间复杂度：。没有使用额外数组空间。

3.4 提交结果

图2 双指针法代码执行结果

4 解法二：前移法

        前移法是由双指针法扩展出来的一种方法，与双指针法有着相似的思想。

4.1 解题思路

        设置指针right，从数组nums的第3个元素开始遍历，使用变量k记录需要移除的元素的个数，将需要移动的元素前移k个位置。

4.2 设计代码

#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累计删除的元素个数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 复杂度分析

• 时间复杂度：。while循环遍历了一遍数组nums的元素。
• 空间复杂度：。没有使用额外数组空间。

4.4 提交结果

图3 前移法代码执行结果

5 解题心得

• 让有序数组nums中重复出现的元素只出现两次，是让其只出现一次的变体题目，难度更大。
• 双指针法与前移法之间，可以相互转换。
• 双指针法中，left指针用于放置新元素。