描述
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]
之前的想法是再加一个计数的变量就行了
int removeDeplicates1(int A[], int n)
{
int index = , count = ;
for (int i = ; i < n; i++)
{
if (A[index] != A[i])
{
A[index++] = A[i];
count = ;
}
else
{
if (count <= )
{
A[index] = A[i];
count++;
}
}
} return index + ;
}
后来看到了一个更简洁的做法,这个想法很巧妙啊:因为是排好序的,所以只需拿第三个和第一个比,不同的话保存即可。
int removeDeplicates1(int A[], int n)
{
int index = ;
for (int i = ; i < n; i++)
{
if (A[index-] != A[i])
{
A[index++] = A[i];
} } return index;
}