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]
.
题解:
设置两个变量:右边kepler和前向游标forward。如果当前kepeler所指的元素和它下一个元素相等,那么向A中存入这两个相等的元素,然后将forward置为kepeler+2,向前移动,如果碰到的元素都跟当前kepeler所指的元素相等,就忽略,否则,将kepeler移向forward所指元素,继续循环;如果当前kepeler所指的元素和它下一个元素不相等,那么就把这个元素直接加入A中,kepeler前移,继续循环。
例如题目中给的数组:1,1,1,2,2,3.
初始kepeler指向第一个1,发现kepeler+1也是一个1,就把forward置为kepeler+2=2,向前探测。探测到index为3的元素时候,发现和kepeler所指的元素不相等,就把kepeler移到索引为3处,继续上述过程,最终得到数组1,1,2,2,3.
代码如下:
public class Solution {
public int removeDuplicates(int[] A) {
if(A == null || A.length == 0)
return 0;
int kepeler = 0,forward = 0;
int NewSize = 0; while(kepeler < A.length){
if(kepeler+1 < A.length && A[kepeler+1] == A[kepeler]){
A[NewSize++] = A[kepeler]; //相同的元素有两个,都放入数组中
A[NewSize++] = A[kepeler];
forward = kepeler+2;
while(forward < A.length && A[forward] == A[kepeler])
forward++;
kepeler = forward;
}
else if(kepeler < A.length){
A[NewSize++] = A[kepeler];
kepeler++;
}
}
return NewSize;
}
}