@kuailezhishang
2014-12-10T20:08:42.000000Z
字数 618
阅读 2145
Leetcode
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].
给定一个有序表,每个元素最多出现两次。删除掉多余的元素,返回剩余元素的个数。
两个指针,一个指向合法位置的下一个位置 (index)
,另一个用于遍历元素 (i)
。两个指针之间的是无效元素。
这个时候判断 i
指向的元素和 index - 2
指向的元素是否相同。
i
指向的元素是多余无效的。 i
后移即可。i
指向的元素是有效的,即出现次数不多于2次。此时,用 i
替换 index
即可。index
需要后移。
class Solution {
public:
int removeDuplicates(int A[], int n) {
int deleted = 0; //已经删除的元素个数
if(n < 3) //最多含有2个元素,一定满足题意
return n;
int index = 2; //可能不合法的位置
for(int i = 2; i < n; i++)
{
if(A[i] != A[index - 2] )
A[index++] = A[i];
}
return index;
}
};