Remove Duplicates from Sorted Array II
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].
解法一：
我是Pick One!的，所以一开始没关心"Remove Duplicates"中的要求，不知道是排好序的，直接开始做了。
代码比较简单，建立map，存放每个元素与相应的出现次数。
class Solution {
public:
int removeDuplicates(int A[], int n) {
int sum = ;
map<int,int> m;
vector<int> v;
for(int i = ; i < n; i ++)
{
map<int,int>::iterator it = m.find(A[i]);
if(it == m.end())
{
m.insert(map<int,int>::value_type(A[i], ));
v.push_back(A[i]);
sum ++;
}
else if(it->second == )
{
it->second ++;
v.push_back(A[i]);
sum ++;
}
else
{
it->second ++;
}
}
for(vector<int>::size_type st = ; st < v.size(); st ++)
A[st] = v[st];
return sum;
}
};
解法二：
后来发现是排好序的，那么使用in-place做法就可以了。
使用index记录新的A数组下一个的位置，使用i扫描原始A数组。
核心思想就是：
如果i扫到的当前元素在index之前已经存在两个（注意，由于A是排好序的，因此只需要判断前两个就行），
那么i继续前进。否则将i指向的元素加入index，index与i一起前进。
class Solution {
public:
int removeDuplicates(int A[], int n) {
if(n < )
return n;
int index = ;
for(int i = ; i < n; i ++)
{
if(A[i] != A[index-])
A[index ++] = A[i];
}
return index;
}
};