目录
- 一.题目解析
- 二.解法一
- 三.解法二
一.题目解析
首先我们先看一下题目描述:
删除数组中的重复项的升级版要求,一个升序数组序列中,相同的元素最多出现两次。
二.解法一
首项我们先来看一种比较繁琐坑比较多的解法:
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() < 3) {
return nums.size();
}
auto a1 = nums.begin();
auto a2 = nums.begin() + 1;
auto a3 = nums.begin() + 2;
while (a3 != nums.end()) {
while ((a2 + 1) != nums.end() && *a1 == *a2 && *a2 == *a3) {
if (a3 == nums.end()) {
break;
}
nums.erase(a3);
}
if ((a2 + 1) == nums.end())
break;
a1++;
a2++;
a3++;
}
return nums.size();
}
};
首先当数组大小小于3时,这时的数组数据无论是什么都会满足题目的要求,所以直接返回即可。接下来在while的处理中如果a1等于了a3的数据我们则删除a3,其中涉及指针的越界访问会比较麻烦。这个解法简单了解下即可。
三.解法二
解法二我们运用到了双指针的知识:
class Solution {
public: int removeDuplicates(vector<int>& nums) {
if(nums.size()<3)
{
return nums.size();
}
int f = 0;
for (int b = f + 2; b < nums.size(); b++) {
if (nums[f] != nums[b]) {
nums[f + 2] = nums[b];
f++;
}
}
return f + 2;
}
};
首先同样数组大小小于3时直接返回即可,我们用f来表示已经处理好了数组长度,b用来表示遍历的进度。-2则代表了题目要求的最多连续两个相同元素。大家可以调试体会一下,一般这题即是想到双指针也会使用计数的方法,上面的解法还是很巧妙的。