## Wednesday, January 6, 2016

### LeetCode - Remove Duplicates from Sorted Array II (Java)

LeetCode – Remove Duplicates from Sorted Array II (Java)
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].

``` public int removeDuplicates(int[] A) {
if (A.length <= 2)
return A.length;

int prev = 1; // point to previous
int curr = 2; // point to current

while (curr < A.length) {
if (A[curr] == A[prev] && A[curr] == A[prev - 1]) {
curr++;
} else {
prev++;
A[prev] = A[curr];
curr++;
}
}

return prev + 1;
}```
http://n00tc0d3r.blogspot.com/2013/05/remove-element-from-arraylist.html
So, if you simple change the condition to `if (A[i] == A[i-1] && A[i] == A[i-2])`, you are trapped!

Why?

In the above problem, we only need to test the one right before the current one which is not possible to have been overwritten. But now, we also need to test the one that is two nodes away which is possible to have been overwritten. That said, we should test the two nodes that are supposed to be ahead of the current node in the new array.
`````` public int removeDuplicates(int[] A) {
int count = 0;
for (int i=2; i<A.length; ++i) {
if (A[i] == A[i-count-1] && A[i] == A[i-count-2]) { // skip duplicates
++count;
} else if (count > 0) { // copy over non-duplicates
A[i-count] = A[i];
}
}
return A.length - count;
}``````
http://www.jiuzhang.com/solutions/remove-duplicates-from-sorted-array-ii/
```    public int removeDuplicates(int[] nums) {
if(nums == null)
return 0;
int cur = 0;
int i ,j;
for(i = 0; i < nums.length;){
int now = nums[i];
for( j = i; j < nums.length; j++){
if(nums[j] != now)
break;
if(j-i < 2)
nums[cur++] = now;
}
i = j;
}
return cur;
}```
http://blog.csdn.net/linhuanmars/article/details/24343525

```public int removeDuplicates(int[] A) {
if(A==null || A.length==0)
return 0;
int idx = 0;
int count = 0;
for(int i=0;i<A.length;i++)
{
if(i>0 && A[i]==A[i-1])
{
count++;
if(count>=3)
continue;
}
else
{
count = 1;
}
A[idx++]=A[i];
}
return idx;
}```
http://simpleandstupid.com/2014/11/06/remove-duplicates-from-sorted-array-ii-leetcode-%E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/
`    ``public` `int` `removeDuplicates(``int``[] A) {`
`        ``int` `len = A.length;`
`        ``if``(len <=``2` `) ``return` `len;`
`        ``int` `index = ``2``;`
`        ``for``(``int` `i = index; i < len; i++){`
`            ``if``(A[i] != A[index-``2``]){`
`                ``A[index] = A[i];`
`                ``index++;`
`            ``}`
`        ``}`
`        ``return` `index;`
`    ``}`