删除有序数组中的重复元素，返回数组的新长度,但允许最大重复次数为2

124 阅读 0 评论 82 点赞

我是靠谱客的博主舒心香氛，这篇文章主要介绍删除有序数组中的重复元素，返回数组的新长度,但允许最大重复次数为2，现在分享给大家，希望可以做个参考。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/************************************************************************************
**description:删除有序数组中的重复元素，返回数组的新长度,但允许最大重复次数为2
**
如：Input:a={2,2,2,15}
Output:len=3,a={2,2,15}
************************************************************************************/
#include <iostream>
#include <vector>
using namespace std;
//方法一：用index标识新数组的索引，遍历数组元素，当前元素与新数组的倒数第二个元素不同时，将其加入新数组
//时间复杂度O(n),空间复杂度O(1)
int removeDuplicates2_1(vector<int>& arr)
{
if (arr.size() <= 2)
return arr.size();
int index = 1;
for (int i = 2; i < arr.size(); i++)
{
if (arr[i] != arr[index - 1])
arr[++index] = arr[i];
}
return index + 1;
}
//方法二：遍历数组元素，当前元素与它前一个和后一个都相等时，该数不加入
//时间复杂度O(n),空间复杂度O(1)
int removeDuplicates2_2(vector<int>& arr)
{
if (arr.size() <= 2)
return arr.size();
int index = 0;
for (int i = 0; i < arr.size(); i++)
{
if (i > 0 && i < arr.size() - 1 && arr[i] == arr[i - 1] && arr[i] == arr[i + 1])
continue;
arr[index++] = arr[i];
}
return index;
}